2 x n 타일링/C++

프로그래머스

가로의 길이가 n일 때 타일을 배치할 수 있는 방법의 수는 아래와 같이 변화한다.

n = 1		1가지
n = 2		2가지
n = 3		3가지
n = 4	문제 설명 참조	5가지
n = i		DP[i-1] + DP[i-2]

즉 이 문제도 동적 계획법을 이용해 풀 수 있다.

식을 세워보면 DP[i] = DP[i-1] + DP[i-2]가 되므로 이를 가지고 길이가 n인 직사각형에 타일을 배치하는 방법의 수를 구하면 된다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int DP[60001];
    
    DP[1] = 1;
    DP[2] = 2;
    
    for(int i = 3; i <= n; i++) 
        DP[i] = (DP[i-1] + DP[i-2]) % 1000000007; 
    
    return DP[n];
}