[프로그래머스] 프로그래머스 Level3 2 x n 타일링 C++

문제

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

코딩테스트 연습 - 2 x n 타일링

풀이

DP로 해결할 수 있었다. 점화식만 구해주면 레벨3 치고는 그렇게 어렵지 않다.

점화식은 DP(N) = DP(N - 1) + DP(N - 2)이고 그 이유는 DP(5)를 예를들면 DP(5)는 DP(4)에 | 모양 타일을 하나만 넣어주어 만들 수 있고, DP(3)에 -- 모양 타일 두 개를 넣어주면 만들 수 있기 때문이다. 하지만 이런 생각이 들 것이다. DP(3)에 | 모양 타일을 두 개를 넣어줘도 만들 수 있지 않을까? 하지만 DP(4) + | 모양 타일 하나를 통해 만들어진 모양과 이미 겹치기 때문에 이 방법은 개수로 셀 수 없는 것이다.

 

코드

#include <string>
#include <vector>
#define MOD 1000000007

using namespace std;

int dp[60001];

int solution(int n) {
    int answer = 0;

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for (int i = 4; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    answer = dp[n];

    return answer;
}