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