2 x n 타일링

왜 DP를 사용했는가?

타일 한 개의 길이는 2x1이다.
그래서 n이 1일때, 타일을 놓는 방법은 1개이고, n이 2일때, 타일을 놓는 방법은 2개이다. 4개까지 직접 그려서 세어 보면, n이 3일때 3개, n이 4일때 5개이다. 규칙을 보면 DP[4] = DP[3] + DP[2]로 추정해 볼 수 있다.

이때 타일의 크기가 2x1이므로, n이 1 커지면, 그 n을 채우기 위해 n-2의 경우에서 접근하거나 n-1의 경우에서 접근할 수 있다.

어떤 n을 채우기 위해, 놓을 수 있는 경우 중 마지막은 항상 위 두 가지 경우로 좁힐 수 있다.
그리고 위 두 가지 경우는 DP에서 DP[n-2]와 DP[n-1]로 구했다고 친다. 그럼 또 그 경우를 구하기위한 이전 단계들이 있고, 따라 들어가면 끝에가서 DP[1]과 DP[2]가 있다. 그러므로 DP[n]은 DP[n-1] + DP[n-2]라고 할 수 있다....? -> DP[1]과 DP[2]를 미리 저장하고 DP[3], DP[4] ....로 증가하며 저장된 값을 활용해 연산 시간과 메모리를 절약한다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    /*
    n = 1 -> 1
    n = 2 -> 2
    n = 3 -> 3
    n = 4 -> 5
    n = 5 ->
    n = 6 -> 
    */ 
    
    int i;
    vector<int> DP(60001, 0);
    
    DP[1] = 1;
    DP[2] = 2;
    for(i = 3; i <= n; i++){
        DP[i] = (DP[i-1] + DP[i-2]) % 1000000007;
        cout <<  DP[i] << " ";
    }
    answer = DP[n];
    
    return answer;
}