11726 : 2×n 타일링
문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 풀이방법먼저 식을 세워야하는데 d[n]을 어떻게 표현할 수 있을지 생각해보아야 한다. d[n]은 크게 2가지 경우로 나누어 질 수 있다. 1. 끝이 2x1 블록으로 끝나는 경우2. 끝이 1x2 블록 2개로 끝나는 경우 이 두가지 경우 외에 올 수 있는 경우는 없다. 이 두가지 경우를 다르게 말하면 아래와 같다. 1. d[n-1] 끝에 2x1 블록이 추가되는 경우2. d[n-2] 끝에 1x2 블록 2개가 추가되는 경우 따라서 식은 d[n] = d[n-1] + d[n-2]로 유추할 수 있다 출처 : https://www.youtube.com/..
알고리즘/다이나믹프로그래밍
2017. 2. 23. 16:41