백준 (1) 썸네일형 리스트형 [DP] 다이나믹 프로그래밍 타일링 문제 (11726, 11727, 2133) 11726 위 문제를 그림으로 나타내면 아래와 같다. 이와 같이 2*n의 타일을 2*1과 1*2 타일로 채워넣으면 되는 것이다. 처음 다이나믹 프로그래밍을 배우고 푸는 문제라 직접 경우의 수를 다 따져가며.. ㅎㅎ.. 풀려고 했었다.. (삽질) 이는 너무 복잡하게 생각할 필요없이 아래와 같이 풀면 된다. 말로 설명해보면, 2*n의 타일을 채우는 것은 결국 2*n-1의 타일에 2*1을 하나 붙인 것과 2*n-2 타일에 1*2 타일을 두개 붙인 것과 같기 때문에, 이를 점화식으로 쓰면 D[n] = D[n-1] + D[n-2] 과 같게 된다. 이를 코드로 작성하면 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #define _CRT_S.. 이전 1 다음
