BaekJoon 11726 2xn 타일링

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

소스결과 1984 KB / 0 ms

출처 Backjoon

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

2 x n 에 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 문제

DP의 기초를 다지기에 좋은 문제

 

먼저 결론부터 말하면 위 문제는 피보나치 수열의 형태를 띈다

2 x 5까지 경우의 수를 계산해 보면 피보나치 수열의 형태를 가진다

 

주의할 점은 경우의 수를 10007로 나눈 나머지를 구해야 한다.

피보니치 수열을 계산 한 후에 꼭 % 10007 연산을 통해 나머지를 저장하도록 하자

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000;

int main()
{
	int dpTable[MAX + 1];
	int n;

	cin >> n;

	dpTable[0] = 1;
	dpTable[1] = 2;
	
	for (int i = 2; i < MAX; i++)
		dpTable[i] = (dpTable[i - 1] + dpTable[i - 2]) % 10007;
		
	cout << dpTable[n - 1];
	return 0;
}

 

연관 문제

1003 - 피보나치 수열 ( https://www.acmicpc.net/problem/1003 )

2193 - 이친수 ( https://www.acmicpc.net/problem/2193 )