[ 백준11726 - 2xN 타일링 ]

문제 분석

1. DP

시간 복잡도

구현

테이블 정의

D[N] =  2 * N 크기의 정사각형을 채우는 경우의 수

점화식 정의

D[N] = D[N-1] + D[N-2]

초기값의 정의

D[1] = 1
D[2] = 2

헤맸던 부분

분명히 전에 한번 풀어보았던 문제인데 다시 풀지를 못했다.

점화식 유도를 아예 하지 못했다.

얻은 것

DP 유형 학습

전체 코드 [ 내 코드 ]

#include <iostream>
using namespace std;

int T[1002]; // 1-indexed

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int N;

void get_input(){
    cin >> N;
}


int main(void){
    init();
    get_input();

    T[1] = 1;
    T[2] = 2;

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

    cout << T[N] << "\n";

    return 0;
}

느낀점

DP는 경험치...?

참조

바킹독님의 유튜브 강의

유튜브 강의 영상
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.

동빈나님의 유튜브 강의

유튜브 강의 영상
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.