2133_타일 채우기

Concept & Idea

처음 주어진 32의 타일의 경우의 수가 3개이다.
하나 하나 쪼개서 생각해보면, 맨 처음 타일이 왔을 때 뒤에 3개를 다시 붙이면 다른 경우의 수를 만들 수 있다.
그래서 바로 생각할 수 있는 예시가, 3dp[i-2]이다.
그런데 이 3개만으로 끝나지 않고, 새로운 경우의 수가 2개씩 더 생겨난다.
그래서 2dp[i-4]+ 2dp[i-6]등등을 더해가는 것으로 문제를 해결 할 수 있었다.
dp[0]을 1로 초기화해 둠으로 해결할 수 있었다.

Code

#include <iostream>
using namespace std;
int n;
int dp[31];
int main() {
    cin>>n;
    dp[0]=1;
    dp[2]=3;
    for(int i=4; i<=n; i++) {
        for(int j=1; j*2<=i; j++) {
            if(j==1) {
                dp[i]+=dp[i-j*2]* 3;
            } else {
                dp[i]+=dp[i-j*2]* 2;
            }
        }
    }
    cout<<dp[n]<<endl;
}

 

Fealing

문제를 고민해보는 시간을 좀 더 늘릴 필요성이 있을 것 같다..
차근 차근 생각해보면 혼자 생각할 수 있었을 것 같다.