백준 2133 타일 채우기

문제

풀이전략

1. 이 문제는 조금 독특한게 항이 계속 될 수록 새로운 경우의 수가 생긴다. 지금까지의 문제와 다른 점은 n==4일때 또 새로운 모양이 생기고, n==6일때 또 새로운 문양이 생기는 것이다. 따라서 이에따라 새롭게 값들을 더해주어야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int dp[31];

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    

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

    cin >> N;
    for(int i=4; i<=N; i++){
        dp[i] = dp[i-2] * 3;
        for(int j=4; j<=i; j+=2){
            dp[i] += dp[i-j] * 2;
        }
    }
    cout<<dp[N]<<endl;
    return 0;
}

소감

내가 틀렸었고, 매우 중요한 문제이므로 다시한번 꼼꼼히 확인하도록 하자.