[C언어] 백준 9095 : 1, 2, 3 더하기

백준 9095 : 1, 2, 3 더하기

 

문제 링크

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

문제 내용

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

단, 0 < n < 11 인 정수

 

 

Idea

정수 4를 1, 2, 3의 합으로 나타낼 때 마지막 수를 기준으로 정렬해본다.

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

• 1+1+2
• 2+2

• 1+3

이런 식으로 정렬했을 때,

마지막으로 1을 더하는 경우는 마지막 1을 제외하고 3을 만드는 경우의 수와 같고,

마지막으로 2를 더하는 경우는 마지막 2를 제외하고 2를 만드는 경우의 수와 같고,

마지막으로 3을 더하는 경우는 마지막 3을 제외하고 1을 만드는 경우의 수와 같다.

 

즉, 정수 4를 만드는 경우의 수는 3을 만드는 경우의 수, 2를 만드는 경우의 수, 1을 만드는 경우의 수의 합과 같다는 의미다.

 

따라서 점화식은 아래와 같이 만들 수 있다.

• f(n) = f(n-1) + f(n-2) + f(n-3) (단, n>3)

 

 

Code

#include <stdio.h>
 
int main() {
    int dp[11] = { 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 T, n;
    scanf("%d", &T);
 
    //결과 출력
    for (int test_case = 0; test_case < T; test_case++) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
 
    return 0;
}