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

9095 1,2,3 더하기

접근방법

현대 오토에버 대비 다이나믹 프로그래밍 문제중 하나다.

저번 배낭 문제에서 말했듯이 다이나믹 프로그래밍은 문제를 동일한 여러 하위 문제로 쪼개서 푸는 프로그래밍이다.

 

1,2,3 더하기는 주어진 정수 n 만큼 11보다 작은 양의 정수를 입력하고 이 정수가 되는 1 2 3의 합의 경우의 수를 구하는 문제다. 그렇다면 초기 조건은 dp[1]  = 1, dp[2] = 2, dp[3] = 4 이다.(1,2,3을 나타내는 경우의 수) 그렇다면

i정수의 경우의 수는 dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 이렇게 나타낼수있다 왜냐하면

n = 4일때 경우의 수는 7이다

dp[1]은 1이다 

dp[2]은 2이다.

dp[3]은 4이다

이를 보면 dp[4] = 7 이므로 dp 1 2 3 을 더한 값과 같다

다음을 보면 dp[5] = 13 이므로 dp 2 3 4 (2+4+7)을 더한 값과 같다. 이를 통해 점화식을 세우면 

dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 가된다.

 

코드는 다음과 같다  

#include <stdio.h>

int main(void){
    int T, n;
    int dp[12] = {0,};

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

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

    scanf("%d", &T);

    for(int i = 0; i < T; i++){
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }

    return 0;
}