[백준 9095번][C] 1, 2, 3 더하기

문제

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

 

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

---

 

풀이

 

n일 때의 값을 생각해보자

1, 2, 3의 수만 사용할 수 있고, 순서가 다른 방법을 독립적인 방법으로 친다는 것을 생각해야한다

 

무작정 하나씩 세기에는 알고리즘의 속도도, DP의 방법론도 맞지 않는 것 같다

 

그렇다면 이미 세어진 갯수에서 +1, +2, +3 을 뒤에다 붙이는 방법은 어떨까?

 

dp[3]

1 1 1

2 1

1 2

3

일 때,

 

dp[4]

1 1 1 +1

2 1 +1

1 2 +1

3 +1

임을 알 수 있다

 

같은 방법으로 dp[1]에 +3, dp[2]에 +2, dp[3]에 +1 을 붙인다면

dp[4] = dp[1] + dp[2] + dp[3] 임을 알 수 있고

dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 점화식이 도출되는 것을 알 수 있다 

 

---

 

코드

 

#include<stdio.h>

int main() {
    int T, n;
    int dp[11] = {-1, 1, 2, 4,};
    scanf("%d", &T);
    for(int i=0 ; i<T ; i++)
    {
        scanf("%d", &n);
            
        for(int idx=4; idx<=n ; idx++)
        {
            if(dp[idx] == 0)
                dp[idx] = dp[idx-3] + dp[idx-2] + dp[idx-1];
        }
        
        printf("%d\n", dp[n]);
    }
}