[백준] 11726번: 2*n 타일링 [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

【 풀이 】

 

DP 문제이다. 다른 문제들과 마찬가지로 처음부터 경우의 수를 따져가며 규칙성을 찾는 것이 중요하다.

결론적으로는 이 문제는 피보나치수열의 형태를 보인다.

 

N[1] = 1

 

N[2] = 2

 

N[3] = 3

 

N[4] = 5...

• N[1] = 1
• N[2] = 2
• N[3] = 3
• N[4] = 5
• N[5] = 8, N[6] = 13, N[7] = 21, N[8] = 34, N[9] = 55
• 즉 N[n] = N[n-2] + N[n-1].

그리고 문제의 요구대로 계산 과정마다 %10007 을 해주면 된다.

 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

long long int arr[1001];
int main(void)
{
	arr[1] = 1;
	arr[2] = 2;

	int n;
	cin >> n;

	for (int i = 3; i <= n; i++)
		arr[i] = (arr[i - 2] + arr[i - 1])%10007;

	cout << arr[n];

	return 0;
}