C++ / 프로그래머스 / 2 x n 타일링

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

 

문제풀이

 

백준에도 똑같은 문제가 있다. https://www.acmicpc.net/problem/11726

타일의 높이는 2로 고정되어 있고 블록은 가로, 세로 두 가지가 있다.

 

블록은 1x2, 2x1 이렇게 있으므로 두 가지를 생각하면 된다.

-1칸에서 세로로 블록을 채운 가짓수, -2칸에서 가로로 블록을 채운 가짓수를 더하면 된다.

-2칸에서 세로로 블록을 채운 경우는 -1칸에서 세로로 블록을 채운 가짓수와 겹치므로 위의 두 가지 경우만 더하면 된다.

 

코드

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;

int solution(int n) {
    vector<int>DP(n + 1, 0);

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

    for (int idx = 2; idx <= n; ++idx)
        DP[idx] = (DP[idx - 2] + DP[idx - 1]) % MOD;

    return DP[n];
}