문제

image.png

image.png

풀이

문제를 통해 점화식을 정의하면 아래와 같다.

정수 n 을 1,2,3의 합으로 나타내는 방법의 수

예시를 통해서 점화식을 구체적으로 정의 해보겠다.

1 = 1
2 = 1+1, 2
3 = 1+1+1, 2+1, 1+2, 3
4 = 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 3+1, 1+3, 2+2

? + ? + ? ....... + a = n 이 된다.

a=1,2,3으로만 구성이 된다. 마지막 수 a 를 제외한 부분들의 합은
n - a (a=1,2,3) 이 된다.

(n-1) + 1 = n
(n-2) + 2 = n
(n-3) + 3 = 3

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

image.png
dp[1] 의경우, 아무것도 사용하지 않은 경우 + 1을사용하는 경우1가지
dp[2]의 경우, 아무것도 사용하지 않은경우 + 2를 사용하는 경우 1가지, 1을 사용하는 경우 + 1을 사용하는경우 1가지로 총 2가지가 된다.

코드

#include<stdio.h>
int dp[12] = {0,1,2,4};
int main() {

    for(int i = 4; i < 12; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }


    int n;
    scanf("%d",&n);
    while(n--) {
        int a;
        scanf("%d",&a);
        printf("%d\n",dp[a]);
    }    
    return 0;
}