BOJ 2133 타일 채우기

사실 DP 문제는 겁부터 난다. 다른 알고리즘과 마찬가지로 익숙해지고 많이 풀어보면 쉽게 느껴지지만 처음에는 도무지 내 지능이 닿지 못하는 영역인것만 같은 느낌이 들고, 그 좌절감이 참 씁쓸하기 때문이다. DP 문제는 가장 쓴 맛이 컸던 알고리즘이었다. 쉬운 문제부터 천천히 시작하자는 마음으로 만만한 녀석을 골랐다.

---

초기 아이디어

사실 타일 채우기는 DP 의 가장 쉬운 문제인 피보나치와 닮아있다. 다만 이전 타일에서 새로운 경우의 수를 곱해주는 것과 별개로 아예 새로운 배열이 생겨난다는 점을 염두에 두어야 한다. 처음에는 dp[n-2] *3 + dp[n-3] *2 두가지만 고려했었는데, 아예 새로운 배열도 나오겠구나 라는 생각에서 dp[n-2*i]*2 로 전부 더해주어야 한다는 생각에 닿았다.

문제풀이

DP

#include<bits/stdc++.h>
using namespace std;

int dp[31];
int n;
int solve(int k){
    if(k<0)return 0;
    if(~dp[k]) return dp[k];
    int ret = 0;
    k-=2;
    ret += solve(k)*3;
    while(k>=2){
        k-=2;
        ret += solve(k)*2;
    }
    return ret;
}
int main(){
    cin >> n;
    memset(dp, -1, sizeof(dp));
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    cout << solve(n);
}