[BOJ][C++] 백준 11726번 2xn 타일링
Updated:
11726번 2xn 타일링
1. 문제 정보
백준 온라인 저지 [11726번 2xn 타일링] 문제의 링크입니다.
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
1 2 3 4 5
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력1
2
예제 출력1
2
예제 입력2
9
예제 출력2
55
시간 / 메모리 제한
1초 / 256MB
2. 생각
- 2xn의 직사각형의 공간이 있을 때, 가장 오른쪽에 타일을 놓을 수 있는 방법은 총 2가지입니다.
- 하나는 이전에 만들어 놓은 타일(dp[n-1])의 경우에 각각 1x2 타일 한 개 놓는 방법입니다.
1 ... n-1 n dp[n-1] - 다른 하나는 전전에 만들어 놓은 타일(dp[n-2])의 경우에 각각 2X1타일을 두 개 놓는 방법입니다.
1 ... n-2 n-1 n dp[n-2]
예) n이 5일 때, 타일을 채우는 예를 들어보겠습니다.
n=3, 2X3을 채우는 경우 3가지
1 2 3 1 2 3 1 2 3 n=4, 2X4를 채우는 경우 5가지
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1) n=5, 2X3을 채운 타일에 2X1 타일을 두 개 채우는 경우 3가지
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2) n=5, 2X4를 채운 타일에 1X2 타일을 한 개 채우는 경우 5가지
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 따라서, 1)의 경우와 2)의 경우를 더한 8가지 경우가 n번째 타일을 채우는 경우의 수임을 알 수 있습니다.
- 하나는 이전에 만들어 놓은 타일(dp[n-1])의 경우에 각각 1x2 타일 한 개 놓는 방법입니다.
-
n번째의 경우를 구하기 위해 위의 두 가지의 경우를 모두 더합니다. 따라서 점화식 dp(n) = dp(n-1) + dp(n-2) 을 도출할 수 있습니다.
- n으로 입력받을 수 있는 최대 수는 1000이므로 int나 long long으로 표현할 수 있는 범위를 넘어가므로 10007로 나눈 나머지를 저장합니다.
3. 소스코드 (C++)
