[백준 / BOJ / SILVER 1] 15989 번 : 1, 2, 3 더하기 4

지나가던 개발자 2020. 4. 4. 22:57

https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

문제 접근법

이전의 만들 수 있는 방법의 수에 그 다음 수가 추가 되었을 경우 만들 수 있는 경우의 수를 추가하는 방식으로 진행한다.

아래는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <cstdio>
 
int main()
{
    int count, num;
    int nums[] = { 1,2,3 };
    scanf("%d", &count);
 
    while (count--)
    {
        int d[10001] = { 0, };
        d[0] = 1;
        scanf("%d", &num);
 
        for (int i = 0; i < 3; i++)
        {
            for (int j = nums[i]; j <= num; j++)
            {
                d[j] += d[j - nums[i]];
            }
        }
 
        printf("%d\n", d[num]);
    }
 
    return 0;
}
Colored by Color Scripter

 