[baekjoon 11726] 2xN 타일링- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

기본 유형의 DP 문제이다.

DP는 수학적인 접근이 필요해서 연습이 많이 필요한 것 같다.

 

또한, 주어진 문제를 작은 문제로 나눠서 푼 뒤, 결과를 통해 문제를 해결하는 것은 분할 정복과 비슷하다.

하지만 분할 정복은 문제를 분할 시 겹치는 문제가 발생하지 않지만 DP는 겹치는 문제들이 발생한다.

따라서 보통 메모이제이션을 이용해서 같은 문제에 대한 결과가 나오는 함수의 호출을 줄여준다.

 

#include <iostream>

using namespace std;

int n;
int tile[1001];

int dp(int n) {
	if (n < 2)
		return 1;
	if (tile[n] != 0)
		return tile[n] % 10007;
	else
		return tile[n] = ( dp(n - 1)+ dp(n - 2) ) % 10007;
}

int main() {
	cin >> n;
	cout << dp(n);
}

이 문제는 점화식이 결국엔 피보나치와 같게 나오는데

n번째 타일을 채우는 횟수는 f(n-1) + f(n-2)이다.

예를 들어 2*6 타일이라고 생각하면

1. 맨 왼쪽을 2*1타일(세로 타일) 1개로 채운 경우

- 1개의 column을 차지하며 나머지 타일은 2*5의 타일을 구하는 경우가 된다.

세로 타일

 

2. 맨 왼쪽을 1*2타일(가로 타일) 2개로 채운 경우

- 2개의 column을 차지하며 나머지 타일은 2*4의 타일을 구하는 경우가 된다.

가로	타일 1
가로	타일 2

 

따라서 현재 타일 n의 f(n)은 f(n-1)과 f(n-2)를 더해주는 점화식이 완성된다.

나머지 타일(2*5와 2*4)을 채우는 최대 횟수는 이미 구한 횟수끼리 더해 주면 된다.

n이 각각 1과 2일 때는 각각 1과 2이므로 base case로 배열을 채워가면 된다.