목록11727 (1)

코딩뚠뚠

[백준문제풀이] 11727 2xn 타일링 2

풀이일시 : 2020-08-09 ​ 문제 : 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) ​ 출력: 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. ​ 풀이 : 점화식을 만들어보자 가장 마지막에 오는 타일을 생각해봤을 때 가능 한 경우의 수를 생각해본다면 1. 1x2 타일 (그 앞엔 N-1개) 2. 2x1 타일 (그 앞엔 N-2개) 3. 2x2 타일 (그 앞엔 N-2개) 점화식 D[i]=D[i-1]+2*D[i-2] 를 도출해 낼 수 있다. DP에 대한 포스팅이다. 점화식을 쓰는것은 이 알고리즘을 사용한것이다. dbstndi6316.tist..
알고리즘 문제풀이/백준문제풀이 2020. 12. 29. 01:25
이전 Prev 1 Next 다음