[백준 9095] 1, 2, 3 더하기

[백준 9095] 1, 2, 3 더하기

문제 출처 : https://www.acmicpc.net/problem/9095

---

문제

---

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

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의 합으로 나타내는 방법의 수를 출력한다.

예제 입력

3
4
7
10

예제 출력

7
44
274

• 문제 이해하기

1, 2, 3을 이용해서 주어진 정수의 합을 구할 수 있는 수를 구하는 문제다. 우리는 1, 2, 3마다 각각 몇개씩 필요한지 4를 구하는 예제를 통해 알 수 있다.

1은? 1 > '1개'

2는? 1+1 / 2 > '2개'

3은? 1+1+1 / 1+2 / 2+1 / 3 > '4개'

이제 이를 통해서 처음에 주어진 수가 총 몇개가 되는지 알아봐야 한다.

• 계획 및 문제해결

4는 문제 예시를 보면 7개였다. 위의 1,2,3의 개수 규칙을 잘 보면, 4를 구할 때 아래와 같은 방식이 성립된다.

1) 1에서 3을 더할 때 > 3은 4개

2) 2에서 2를 더할 때 > 2는 2개

3) 3에서 1을 더할 때 > 1은 1개

따라서 총 7개가 되는 것이다.

다시 한번 생각해보면, 우리는 1,2,3만 이용해서 합을 구할 수 있는 경우의 수를 구하는 것이 이 문제의 답이다. 역으로 생각하면, 1,2,3을 주어진 수에서 빼는 과정을 통해 구할 수 있다는 것을 알 수 있다. 따라서 점화식으로 나타내면 아래와 같다.

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

반복문을 통해 4부터 입력한 값까지 돌린 후, 점화식을 통해 재귀함수를 돌리면 원하는 값을 얻을 수 있다. 

• 전체 소스 코드

#include <iostream>
 
using namespace std;
 
int main(void) {
    int N, M;
    int arr[11] = { 0 };
 
    arr[1] = 1; //1일 때 경우의 수
    arr[2] = 2; //2일 때 경우의 수
    arr[3] = 4; //3일 때 경우의 수
 
    cin >> N;
 
    while (N >= 1) {
        cin >> M;
 
        for (int i = 4; i <= M; i++) {
            arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
        }
        cout << arr[M] << endl;
 
        N--;
    }
}