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

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

 

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);
    d[1] = 1;
    d[2] = 2;
    for (int i = 3; i <= n; i++) {
        d[i] = (d[i-1] + d[i-2]) % 10007; // int overflow 주의!
    }
    
    cout << d[n];
}

 

 

2. 분석

1. dp 테이블 정의:

d[i] = i번째 타일링 방법의 수

 

2. 점화식:

(1) d[i]에 가로 1 x 세로 2를 놓는 경우: d[i-2]

(2) d[i]에 가로 2 x 세로 1을 놓는 경우: d[i-1]

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

 

dp의 점화식을 만들때는 테이블에서 i번째를 고정하고 점화식을 어떻게 이끌어 낼지 생각하는 것이 중요하다.

 

※ 10007로 나눈 나머지를 출력하라고 했는데 나머지 연산은 덧셈에 대해 닫혀있으므로 dp 테이블에도 나머지로 나눈 값을 계속 저장해줘야한다. 계속 그냥 저장하고 마지막 출력할 때만 나머지 연산을 하려고 하면 이미 숫자가 int 범위를 초과하여 int overflow가 발생한다.

 

3. 시간복잡도

배열 n을 한번만 순회하므로 O(n)이다. n = 1000 < 10^8이므로 시간제한 1초이내로 통과 가능하다.