1) 문제
https://www.acmicpc.net/problem/11726
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
2) 입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
3) 강의 풀이
1) 풀고 싶은 가짜 문제 정의
진짜 문제 : 주어진 N에 대해 2XN 타일링 경우의 수
가짜 문제 : Dy[i] = 2Xi 타일링 경우의 수
2) 초기값은 어떻게 되는가?
Dy[1] = 1
Dy[2] = 2
3) 점화식
Dy[i] = Dy[i-1] + Dy[i-2]
4) 시간복잡도
Dy 배열을 1번부터 N번까지 채우는 O(n) 시간 복잡도로 해결된다.
기록용.