백준 알고리즘 11727번: 2×n 타일링 2 [C++]

문제 출처: www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

1. 코드

#include <iostream>

using namespace std;
int n;
int arr[1001];
int solution(int deep)
{
	if (deep == 0)
		return arr[0] = 1;
	if (deep == 1)
		return arr[1] = 1;
	if (arr[deep])
		return arr[deep];
	else
		return arr[deep] = (solution(deep - 1) + (solution(deep - 2) * 2)) % 10007;
}

int main(void)
{
	cin >> n;

	solution(n);
	cout << arr[n];
	return 0;
}

(실행)

2. 풀이

풀이 방법은 간단하다. 점화식을 찾아내고 그것을 토대로 코드를 작성하여 진행한다. 그리고 arr 배열을 이용하여 경우의 수를 저장하여 이미 저장되어 있는 배열을 접근할 때 해당 배열을 반환을 해서 속도를 최소화 시킨다.

경우의 수는 다음과 같은데 n = 1일 경우 1가지 n = 2일 경우 3가지, n = 3일 경우 5, 이렇게 보면 점화식은 다음과 같이 도출되는데 f(n - 1) + f(n - 2) * 2이다.

3. 느낀 점

점화식만 빠르게 찾을 수 있다면 쉽게 해결할 수 있는 문제이다.