[Baekjoon/C++] 15989번 - 1, 2, 3 더하기 4

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

int arr[10001] = { 1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for (int i = 1; i < 4; i++)
        for (int j = i; j < 10001; j++)
            arr[j] += arr[j - i];

    int T, n;
    cin >> T;

    while (T--) {
        cin >> n;
        cout << arr[n] << '\n';
    }

    return 0;
}

n|i		1	2	3
1		1			1개
2		1	2		2개
3		1	2	3	3개
4		1	3	4	4개
5		1	3	5	5개
6		1	4	7	7개

우선 숫자를 1과 같거나 작은 수로 표현하는 방법은 무조건 1가지이다. arr[0]을 1로 초기화했기에 모든 배열에 arr[i - 1]의 값을 더하면 된다.

그 다음 숫자인 2와 같거나 작은 수로 n을 표현하는 방법의 수를 보면 2와 3은 1가지의 경우를 가지고 있기에 arr[2]와 arr[3]은 2가 된다. 4는 2가지의 경우의 수를 가지고 있기에 arr[4]는 3이 되는데, 이를 보면 arr[n - 2]가 각 숫자들을 2보다 작거나 같은 수로 표현하는 경우의 수가 된다는 것을 알 수 있다.

3의 경우도 마찬가지이기에 각 인덱스에 arr[n - i]를 더하면 된다는 것을 알 수 있다.