[백준 9095 - C++] 1, 2, 3 더하기 : DP

www.acmicpc.net/problem/9095

9095번: 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

예제 입력 1

3

4

7

10

예제 출력 1 

7

44

274

 

 풀이

난 정말 dp가 제일 어렵당... 풀다보면 머리가 아프달까>?ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

아무튼 이 문제에서 가장 중요한 아이디어!!

4이상의 수 n을 1, 2, 3으로 나타내는 것은

<n-1을 나타내는 식 +1>, <n-2를 나타내는 식 +2>, <n-3을 나타내는 식 +3> 이렇게 3가지 라는 것이다.

 

예를 들어 4를 보자

우선 3을 나타내는 식들에 +1을 하면

(1+1+1) +1 , (1+2) +1, (2+1) +1, (3) + 1  => 4가지

2를 나타내는 식들에 +2를 하면

(1+1) +2, (2) +2  =>2가지

1을 나타내는 식들에 +3을 하면

(1) + 3  => 1가지

이렇게 해서 총 방법의 수는 4+2+1 = 7이 된다.

 

이를 일반화하면

방법의수(n) = 방법의수(n-1) + 방법의수(n-2) + 방법의수(n-3) 이된다! 단 이는 n>3일때!

따라서 1, 2, 3까지는 그냥 구해서 배열에 넣어두고 그 뒤부터 for문으로 계산하는 방식으로 구현하였다.

 

#include <iostream>
#include <cstdio>

int count[15];

int main(void){
    int t, n;
    
    count[1] = 1;
    count[2] = 2;
    count[3] = 4;
    
    scanf("%d", &t);
    
    for(int i=0; i<t; i++){
        scanf("%d", &n);
        if(n == 1 || n==2 || n==3){
            printf("%d\n", count[n]);
            continue;
        }
        else{
            for(int j=4; j<n+1; j++){
                count[j] = count[j-1] + count[j-2] + count[j-3];
            }
        }
        printf("%d\n", count[n]);
    }
}