백준 9095 1, 2, 3 더하기(dynamic programming)

 

#include <iostream>
 
using namespace std;
 
int num;
int dp[11];
 
void makeSum()
{
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i < 11; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    makeSum();
    cin >> num;
    while (num--)
    {
        int tmp;
        cin >> tmp;
        cout << dp[tmp] << "\n";
    }
}

1-1개
1
2-2개
1 1               
2                  
3-4개
1 1 1            
1 2               
2 1              
3
4 -7개             
1 1 1 1            
1 1 2             
1 2 1            
2 1 1
2 2 
1 3 
3 1
5-13개     
1 1 1 1 1  
1 1 1 2     
1 1 2 1      
1 2 1 1     
2 1 1 1
1 2 2
2 1 2
2 2 1
1 1 3
1 3 1
3 1 1
2 3
3 2
6 --24개
1 1 1 1 1 1
1 1 1 1 2
1 1 1 2 1
1 1 2 1 1
1 2 1 1 1
2 1 1 1 1
1 1 1 3
1 1 3 1
1 3 1 1
3 1 1 1 
1 1 2 2
1 2 1 2
2 1 1 2
2 1 2 1
2 2 1 1
1 2 2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
2 2 2
3 3

 

dp 문제라는 것을 알고 풀다보니 그냥 쭉 써놓고 점화식을 찾아서 풀었다. dp[i]=dp[i-1]+dp[i-2]+dp[i-3](i>=4)

이 문제는 보고 dp 문제라는 것을 쉽게 알아차릴 수 있을 것 같은데 다른 dp문제를 봤을 때 바로 dp문제임을 알아채고 이런 식으로 풀어낼 수 있을지 조금 걱정이다.