백준 9095 : 1, 2, 3 더하기(DP)

문제 링크입니다 https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

재귀 호출로 풀어봤던 이 문제를 dynamic programming으로 풀어봤습니다. "D[N] : N을 1, 2, 3의 합으로 나타내는 방법의 개수"라 했을 때, 맨 끝에 오는 수는 1, 2, 3 세 개가 올 수 있습니다.

 

즉,

[1] O + O + ... + 1 = N

[2] O + O + ... + 2 = N

[3] O + O + ... + 3 = N

이러한 형태로 나타낼 수 있고,

 

그러므로,

[1] D[N-1] + 1 = N

[2] D[N-2] + 2 = N

[3] D[N-3] + 3 = N

이렇게 표현 가능하며, 이 경우를 모두 더하면 N을 1, 2, 3의 합으로 나타내는 모든 경우를 고려한 값이 됩니다.

 

결국, "D[N] = D[N-1] + D[N-2] + D[N-3]" 이라는 점화식을 얻을 수 있게 됩니다.

 

 

[소스코드]

 

#include<cstdio>
 
// dp[n] : n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수
int tc, n, dp[11];
 
int main(void) {
 
    // 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수는 각각
    // 1은 1개, 2는 2개, 3은 4개 입니다
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
 
    // 4부터는 점화식을 활용하여 모든 수에 대해 구해줍니다
    for (int i = 4; i <= 10; i++) 
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
    scanf("%d", &tc);
    for (int i = 0; i < tc; i++) {
        scanf("%d", &n);
 
        // 각 테스트케이스마다 원하는 값을 출력합니다
        printf("%d\n", dp[n]); 
    }
    return 0;
}