[BOJ / C++] 2×n 타일링 2 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/11727

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<int> d(n+1, 0);
    d[1] = 1;
    d[2] = 3;

    for (int i = 3; i <= n; i++) {
        d[i] = (d[i-1] + 2*d[i-2]) % 10007;
    }
    
    cout << d[n];
}

 

 

2. 시간복잡도

n = 1000이므로 dp를 이용해서 푼다면 시간제한 1초 내에 통과 가능하다. dp 테이블을 채우는데 O(n)이고, n = 1000 < 10^8이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

[boj_11726.cpp] 2×n 타일링 (다이나믹 프로그래밍)

 

다이나믹 프로그래밍 문제이다. 위 문제와 매우 유사하다.

 

1. dp 테이블 정의:

i번째 칸을 채울 수 있는 방법의 수

 

2. 점화식:

(1) i번째에 2x1 사각형을 채우는 경우: d[i-1]

(2) i, i-1에 걸쳐 2x1 또는 2x2를 채우는 경우: d[i-1] x 2가지(2x1, 2x2)

 

따라서 d[i] = d[i-1] + 2*d[i-2] 이다.