[11726] C++ : 2 x n 타일링

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

2

예제 출력 1 

2

예제 입력 2 

9

예제 출력 2 

55

 

풀이

처음에 이 문제를 보고 든 생각이 엥...? 이거 어떻게 푸는거냐 였다. 그래서 결국 하나씩 다 그려보기로 했다. 

그러다가 너무 귀찮아서.. 숫자로 표현해보았다. 세로블럭(1X2) 는 1로 가로블럭 2개 (2X1 2개 = 2X2)는 2로 표시했다.

1 : 1 -> 1개
2 : 11 / 2 -> 2개
3 : 111 / 12 / 21 -> 3개
4 : 1111 / 211 / 121 / 112 / 22 -> 5개
5 : 11111 / 2111 / 1211 / 1121 / 1112 / 221 / 212 / 122 -> 8개
...

이렇게 나열해보니 규칙이 보이지 않는가?
5 에서 11111 / 2111 / 1211 / 1121 / 221 은 4의 요소의 오른쪽에 1을 붙인 것이고, 1112 / 212 / 122 은 3의 요소에 1을 붙인 것이다.

즉, 2XN 크기의 직사각형을 채우는 방법은 N-1과 N-2개의 방법을 더한 것과 같다. 즉, 피보나치와 동일한 문제임을 알 수 있다. 

이제 문제가 간단해졌다. 풀이는 아래와 같다. 피보나치는 bottom-up으로 해결하는 것이 빠르다. 

#include<iostream>
#define MAX 1001

long long arr[MAX] = { 0 };

int main()
{
	int n;
	std::cin >> n;
	arr[1] = 1;
	arr[2] = 2;
	for (int i = 3; i <= n; i++)
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	printf("%lld", arr[n]);
}

주의할 점은 10007의 나머지로 연산해야한다는 점이다. 저 조건이 붙었던 이유는 당연히 overflow가 발생했기 때문이고, 처음에는 결과에 10007로 나누었는데 이미 오버플로우가 나서 실행이 안되었다. 연산 중에 10007의 나머지를 더해주어야지 잘 작동할 것이다.