백준 11726번 문제 : 2xn 타일링

문제 링크 : 백준 11726번 : 2xn 타일링

이 문제는 n을 입력받아 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 문제이다. Dynamic Programming으로 풀 수 있는 문제이고, 생각보다 간단한 문제였다. 나는 일단 규칙을 찾기 위해 그림으로 그려보았더니, 피보나치 수열과 비슷한 규칙이 나왔다.

DP로 문제를 풀기 위해, d[n]배열에 경우의 수를 저장한다. 먼저, d[0] = 1, d[1] = 1 로 초기화를 해 준다. 그림으로 그려 풀어보니, 그림으로도 규칙을 찾을 수 있었다.

• d[n] = d[n-2]의 직사각형 오른쪽에 누운 직사각형 2개가 붙은 경우의 수 + d[n-1]의 직사각형 오른쪽에 세운 직사각형 1개가 붙은 경우의 수

따라서, 간단히 점화식으로 표현하면 d[n] = d[n-1] + d[n-2] 가 될 수 있겠다.

문제에서 10007로 나눈 나머지를 출력하라고 되어 있고, 계속해서 더하다 보면 숫자가 너무 커져 자료형의 크기를 넘을 수 있기 때문에, d[n]을 구할 때 10007로 나눈 나머지를 저장해주어야 런타임 에러를 방지할 수 있다.

Bottom-up 방식을 사용하였다.

#include <iostream>
using namespace std;

int main()
{
	int n;
	int d[1001];
	cin >> n;
	d[0] = 1; d[1] = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = (d[i - 1] + d[i - 2]) % 10007;
	}
	cout << d[n];
	
    return 0;
}