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

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

11726번: 2×n 타일링

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)) % 10007;
}

int main(void)
{
	cin >> n;

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

(실행)

2. 풀이

문제 그대로 그려보면 n = 1일 때는 1가지이고, n = 2일 때는 2가지, n = 3일 때는 3가지 이렇게 진행이 되는데 어딘가 익숙하지 않은가? 피보나치수열과 방식이 동일하다. 그렇다면 계속해서 예제 입력인 9까지 진행을 하면 55가 나온다. 그렇다면 점화식은 f(n - 1) + f(n - 2)이다.

그런데 동적 계획법을 이용하여 문제를 해결하기 위해서 arr이라는 배열에 경우의 수를 저장해두어 배열에 해당하는 값이 있다면 배열에서 값이 반환하게 한다. 그리고 문제에서 100007로 나눈 나머지 값으로 출력을 하라고 했기 때문에 arr 배열에 새로운 값을 저장할 때 % 10007을 해준다.

3. 느낀 점

dp 문제를 아직 잘 못 풀지만 이번 문제는 상대적으로 쉬웠던 것 같다.