[DP] 백준 11726, 11727 - 2xn 타일링

DP - 다이나믹 프로그래밍

 

구하기

 

1) n이 1,2,3.. 일때의 규칙성을 찾는다.

 

n=1 답:1

 

n=2 답:2

 

 

n=3 답:3

 

 

 

2) 점화식 구하기

 

 

// BJ - 11726 2*n 타일링
// 다이나믹 프로그래밍

#include <iostream>
using namespace std;

int arr[1001];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 2;
	if (arr[x] != 0) return arr[x];
	
	return arr[x] = (dp(x - 1) + dp(x - 2)) % 10007; 
	//%10007은 오버플로우 방지
}

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

 

비슷한 문제 

11727

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

// BJ - 11727 타일 문제 2 : DP

#include <iostream>
#using namespace std;

int arr[1001];

int dp(int x) {

	if (x == 1) return 1;
	if (x == 2) return 3;
	if (arr[x] != 0) return arr[x];

	return arr[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007;
}


int main() {

	int n;
	cin >> n;

	cout << dp(n);

}