11726

백준 11726번

Link: 11726번: 2×n 타일링

---

문제 설명

풀이가 짧은 시간안에 명쾌하게 나온 DP 문제다.

가로 2, 세로 1짜리 타일을 회전시키거나 회전시키지 않는 식으로 붙여가면 되는 문제.

처음에는 아무 생각없이 시도했다가 틀렸는데, 다음 타일을 반드시 현재 타일셋의 맨 오른쪽에다가 붙인다는 생각으로 푸니 바로 풀렸다.

이점만 조심하면 무난했던 DP 문제였다.

---

정답 코드

//
// Created by Keith_Lee on 30/03/2019.
//

#include <iostream>

using namespace std;

int main(){
    int N;

    long long DP[1001][2] = {0, };

    DP[1][0] = 1;
    DP[1][1] = 0;
    DP[2][0] = 1;
    DP[2][1] = 1;

    cin >> N;

    for(int i=3; i<=N; i++){
        DP[i][0] = (DP[i-1][0] + DP[i-1][1]) % 10007;
        DP[i][1] = DP[i-1][0] % 10007;
    }

    cout << (DP[N][0] + DP[N][1]) % 10007 << '\n';

    return 0;
}

---