[BOJ] C++ 11726: 2xn 타일링 - DP 기초

11726번: 2×n 타일링

예제

9

ans : 55

---

문제를 처음 봤을 때 바로 dp로 풀어야겠다 생각한 건 아니고 완전 탐색으로 셀 수 있나 생각을 해 봤다. 타일을 완전 탐색으로 채우는 것 자체가 힘들어 보여서 일단 손으로 보드를 채워보면서 문제를 파악했다.

딱 정확히 이 사진의 흐름대로 2*3에서도 2*2와 2*1을 이용해서 채운 느낌이 들었고 2*4 블록을 채울 때 확신이 생겼다.

 

2*k 블럭을 예로 들자면, 세로로 긴 블록을 하나 먼저 세우면 나머지 k-1열 2*k-1 블록을 채우는 방법과 정확히 똑같다. 그리고 가로로 긴 블록 두 개를 세우면 2*k-2 블록을 채우는 방법과 정확히 똑같다. 2*k 블록을 채우는 방법은 이 두 가지로 명확하게 나누어지므로 dp로 풀면 피보나치 수열이랑 똑같이 구현하면 바로 풀릴 것 같아서 그렇게 구현했다.

 

이처럼 dp의 핵심은 다음과 같다.

1. 테이블링 잘하기
2. 초기 조건 세팅하기
3. 점화식 찾기

마치 재귀처럼 문제를 계속 풀면서 위의 세 조건만 딱딱 맞춰주면 가볍게 풀린다.

/** DP 11726 2xn 타일링 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;
int dp[1002];

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

    cin >> n;
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++)
        dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
    cout << dp[n - 1];
}