연습문제 > 2 x n 타일링

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

DP 문제이다.

왜냐하면 i칸을 채우는 방법은 i-1 칸을 채우는 방법과 i-2 칸을 채우는 방법을 더한 것과 같으므로 점화식으로 풀 수 있다.

이는 결국 마지막 칸을 마무리하는데 있어 세로 두 칸 가로 한 칸 짜리 블록으로 채울 것인가 세로 한 칸 가로 두 칸짜리 블록을 쌓아 넣을 것인가로 갈리는데서 기인힌다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<int> DP = {1, 1, 2};
    for(int i = 3; i<=n;i++){
        int tmp = DP[i-1]+DP[i-2];
        tmp %= 1000000007;
        DP.push_back(tmp);
    }
    return DP.back();
}