[백준문제풀이] 11727 2xn 타일링 2

 

풀이일시 : 2020-08-09

​

 

문제 :

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

​

 

입력:

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

​

 

출력:

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

​

 

풀이 :

점화식을 만들어보자

가장 마지막에 오는 타일을 생각해봤을 때 가능 한 경우의 수를 생각해본다면

1. 1x2 타일 (그 앞엔 N-1개)

2. 2x1 타일 (그 앞엔 N-2개)

3. 2x2 타일 (그 앞엔 N-2개)

점화식 D[i]=D[i-1]+2*D[i-2] 를 도출해 낼 수 있다.

 

DP에 대한 포스팅이다. 점화식을 쓰는것은 이 알고리즘을 사용한것이다.

dbstndi6316.tistory.com/35?category=953970

[개념정리] DP 동적프로그래밍

​

#include <iostream>
using namespace std;
int d[1001];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 3; //3가지 경우의 수
	if (d[x] != 0) return d[x];
	return d[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007; //N-2개가 남는 상황이 두개가있음
}

int main() {
	int x;
	cin >> x;
	printf("%d", dp(x));
}