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

문제링크

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

문제

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

조건

• 시간 제한 : 1s

• 메모리 제한 : 512MB

---

해설

숫자 N을 구성하기 위해 마지막으로 선택한 동전의 종류에 따라 1인 경우, 2인 경우, 3인 경우에 대해 N-1, N-2, N-3을 구성하는 경우의 수를 이용하면 1, 2, 3의 합으로 나타내는 방법의 수를 쉽게 구할 수 있다.

풀이

다이나믹 프로그래밍 방식을 적용하여 풀면 쉽게 해결이 가능한 문제이다.

다이나믹 프로그래밍을 적용하기 위한 조건은 1. 작은 문제가 반복적으로 일어나고, 2. 같은 문제의 답은 항상 같아야 하는데, 이 문제에서는 N에 대해서 N-1, N-2, N-3으로 문제를 나누어 작은 문제를 통해 큰 문제를 해결할 수 있어 적용하기에 적절하다.

4를 예로 들어보자.
1. 3을 마지막으로 선택한 경우 (1에 3 추가)
		1 +3
2. 2를 마지막으로 선택한 경우 (2에 2 추가)
		1+1 +2
		2 +2
3. 1을 마지막으로 선택한 경우 (3에 1 추가)
		1+1+1 +1
		1+2 +1
		2+1 +1
		3 +1
→ 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 3+1 1+3 모두 커버 가능

위 예시를 통해 N의 경우의 수는 N-1의 경우의 수 + N-2의 경우의 수 + N-3의 경우의 수와 같음을 알 수 있다. 이를 식으로 옮기면 아래와 같다.

arr[N] = arr[N-1] + arr[N-2] + arr[N-3];

k가 3보다 작거나 같은 경우에는 1, 2, 3 동전을 추가하는 특수한 경우이므로 예외처리 하였고, 나머지 k가 3보다 큰 경우에 대해서 일반항을 적용하여 값을 구한 뒤, 구하고자 하는 N의 값을 구한다.

int n;
cin >> n;
vector<int> arr(n+1);

for(int k = 1; k <= n; k++) {
    if(k > 3) {
        arr[k] = arr[k-1] + arr[k-2] + arr[k-3];
    } else{
        if(k==1) arr[k] = 1;
        else if (k==2) arr[k] = 2;
        else arr[k] = 4;
    }
}

printf("%d\n", arr[n]);

---

코멘트

매우 단순하고 쉬운 DP문제!

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main () {
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector<int> arr(n+1);
        
        for(int k = 1; k <= n; k++) {
            if(k > 3) {
                arr[k] = arr[k-1] + arr[k-2] + arr[k-3];
            } else{
                if(k==1) arr[k] = 1;
                else if (k==2) arr[k] = 2;
                else arr[k] = 4;
            }
        }
        printf("%d\n", arr[n]);
    }

    return 0;
}

Uploaded by Notion2Tistory v1.1.0