Problem
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
문제를 고민해보는 시간을 좀 더 늘릴 필요성이 있을 것 같다..
차근 차근 생각해보면 혼자 생각할 수 있었을 것 같다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.