[DP] BOJ 11727 2Xn 타일링 2 - 오답노트

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

11727번: 2×n 타일링 2

- 문제 파악

정수 N 이 주어지고 1x2 , 2x1 , 2x2 타일로 N을 채우는 경우의 수 출력

 

- 나의 접근

조합 알고리즘으로 접근해서 예제는 맞았지만 1000이 틀렸다.

이전에 11726번을 풀다가 틀렸음에도 뭔 자신감인지 복습 안하고 풀었다가 당했다.

그때랑 비슷하게 당한거 같은데..

앞으로는 이렇게 풀자..

다이나믹 프로그래밍(DP)은 점화식이다..

 

-정답

#include "bits/stdc++.h"
using namespace std;

int main() {
	int n;
	cin >> n;
	int D[1001];
	D[1] = 1, D[2] = 3;		// n=1, n=2일 때의 2xn 타일링 수
	for (int i = 3; i <= n; i++) {	// n=3부터 n까지 반복
		D[i] = D[i - 1] + (D[i - 2]*2); // 2xn 타일이 두개
		D[i] %= 10007;		// 문제의 조건
	}
	cout << D[n];
	return 0;
}