[C언어] 백준 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

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

9095번: 1, 2, 3 더하기

 

다이나믹 프로그래밍 문제입니다.

4이상의 n값이 들어왔을 때 n을 1, 2, 3 각각의 합으로 나타내는 모든 경우의 수를 구하는 문제인데요.

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

문제 설명부분에 있는 4를 만들 때의 모든 경우의 수 입니다.

아무 생각없이 보면 그런가 보다 하는데 집요하게 봐보세요

무언가 보이지 않으신가요??

 

안보이신다면 이건 어떠신가요??

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

그래도 안보인다면??

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

1+1+2
2+2

1+3

이렇게 분리해서 봐보세요

 

이 정렬을 했을때의 보이는 규칙은

1, 2, 3이 각각 맨 뒤에 있고 맨 뒤에 있는 1, 2, 3을 각각 뺏을 때 3, 2, 1이 됩니다.

즉 3을 만드는 경우의 수는 4, 2를 만드는 경우의 수는 2, 1을 만드는 경우의 수는 1이 됩니다.

지금 이 경우의 수는 4에 대한 경우의 수입니다.

이를 이용해 점화식을 나타낸다면

f(n) = f(n - 1) + f(n - 2) + f(n - 3)

이 되겠습니다.

 

저도 처음에는 이 점화식이 맞을까?? 하면서 5와 6을 직접 경우의 수를 따져 봤습니다.

// n이 5일 때의 모든 경우의 수
1+1+1+1+1
2+1+1+1
1+2+1+1
1+1+2+1
2+2+1
3+1+1
1+3+1

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

1+1+3
2+3

보시면 경우의 수는 13입니다.

4일 때의 경우의 수가 7이였죠

5를 위 점화식에 맞춰서 써보죠

f(5) = 7 + 4 + 2

f(5) = 13

점화식을 대입했을 때 맞는것 같네요

 

하지만 저는 뭔가 찝찝해서 6까지 해봤습니다.

// n이 6일 때의 모든 경우의 수
1+1+1+1+1+1
2+1+1+1+1
1+2+1+1+1
1+1+2+1+1
1+1+1+2+1
3+2+1
2+3+1
3+1+1+1
1+1+3+1
2+2+1+1
2+1+2+1
1+2+2+1

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

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

n이 6일 때의 모든 경우의 수는 24로 보였습니다.

이제 점화식을 적용해 봅시다.

f(6) = 13 + 7 + 4

f(6) = 24

오? 맞네요??

 

사실 6까지 직접 테스트 해본 진짜 이유는

예제 입력 부분에  f(7) = 44 가 있었기 때문인데요

f(7) = f(6) + f(5) + f(4) 이기 때문에

f(7) = 24 + 13 + 7

f(7) = 44

 

이제 f(n) = f(n - 1) + f(n - 2) + f(n - 3)이 맞는 점화식이란것을 알았습니다.

그럼 저희는 이제 이 점화식을 코드에 적용시키기만 하면 됩니다.

 

반응형

전체 코드

#include <stdio.h>

int    t, n, result[11];

int main(void)
{
    scanf("%d", &t);
    result[1] = 1;
    result[2] = 2;
    result[3] = 4;
    for(int i = 4; i < 11; i++)
        result[i] = result[i - 1] + result[i - 2] + result[i - 3];
    for(int i = 0; i < t; i++)
    {
        scanf("%d", &n);
        printf("%d\n", result[n]);
    }
    return (0);
}

"n은 양수이며 11보다 작다." 문제 설명 부분을 봐서 1, 2, 3의 경우의 수를 모두 체크해준 후

10까지 점화식을 적용해줍니다.

이후 n을 입력받고 n일 때의 경우의 수를 출력하면 되는 문제이죠

 

역시 다이나믹 문제는 코드가 짧은데 머리를 잘 써야하나 보네요 ㅠㅠ