[BOJ] 11726 2xn 타일링

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

Note

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 - 피보나치 수열

2019-01-14 11:30:00에 Tistory에서 작성되었습니다.