[프로그래머스] 3 x n 타일링

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

풀이

실패

dp[i] += (dp[i - 2] * 3 + 2) % 1000000007;

위와 같은 점화식을 생각했지만, 놓친 예외가 있어 실제로는 문제를 맞추지 못하고 풀이를 찾아보았다.
해당 블로그에서 풀이를 참조하였다.
물론 레벨4 분류의 어려운 문제였지만, dp문제를 또 틀렸다는 점에서 경각심이 느껴진다. 집에 알고리즘 책에서 dp챕터를 공부해봐야겠다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    long dp[5001] ={0,};
    dp[2] = 3;
    for(int i = 4; i <= n; i += 2){
        dp[i] += (dp[i - 2] * 3) % 1000000007;
        for(int j = i - 4; j >=2; j -= 2){
            dp[i] += (dp[j]*2) % 1000000007;
        }
        dp[i] = (dp[i] + 2) % 1000000007;
    }
    return (int)(dp[n]);
}