[백준 BOJ][DP] 11727 2xn 타일링 2

11727_2xn 타일링 2

 

링크

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

 

풀이

 

점화식을 세우기 위해서 그림을 그려보겠습니다.

 

 

이렇게 되어 2*n까지 타일을 채우는 방법은 f(n-1) + 2*f(n-2)라는 것을 알 수 있습니다.

점화식은 DP[n] = DP[n-1] + 2*DP[n-2]입니다.

 

DP[1]과 DP[2]는 미리 구해 놓아야 합니다.

 

 

코드로 구현하겠습니다. 주의할 점은 n은 1000까지 -> 배열은 1001로 선언, 출력은 10,007로 나눈 나머지로 해야 합니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

//11727_2xn 타일링 2 #include <iostream> using namespace std;   int DP[1001] = { 0, 1, 3 };   int f(int n) {     if (DP[n]) return DP[n];       return DP[n] = (f(n - 1) % 10007 + 2 * f(n - 2) % 10007) % 10007; }   int main() {     int n;       cin >> n;     cout << f(n) << endl;       return 0; } Colored by Color Scripter

cs