[백준/BOJ/C++] 9095번 1, 2, 3 더하기 - Dynamic Programming

1. 문제

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

2. 입력

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

3. 출력

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

4. 풀이

사용 변수 : T(테스트 케이스 개수), testcase 배열(각각의 테스트 케이스 입력 값을 저장하는 배열), arr 배열(1에서 10까지의 경우의 수를 저장하는 배열)

이 문제는 단순히 1,2,3만 사용하여 자연수의 분할을 나타내는 것이기 때문에 'BOJ 1463번 1로 만들기'문제와 같이 bottom-up방식으로 문제를 해결하면 된다.

위의 그림을 보고 숫자 4를 예시로 들면 4는 1에서 +3, 2에서 +2, 3에서 +1을 한 것과 같다. 거꾸로 생각하면 4의 경우의 수는 4에서 -1, -2, -3을 한 경우의 수의 합과 같다. 문제에서 주어진 입력이 n은 11보다 작기 때문에 최대 10까지의 경우를 구한 다음 각각 테스트 케이스에서 원하는 숫자의 경우의 수를 출력해주면 된다.

1) 먼저 테스트 케이스 개수를 입력받고 그 개수만큼 배열을 할당하여 배열에 각각의 테스트 케이스를 저장한다.

2) for문으로 i는 1부터 10까지 반복하며 그 수에서 1, 2, 3을 뺀 경우의 수를 arr[i]에 더해준다.

3) 마지막으로 저장해뒀던 testcase배열안의 테스트 케이스 값을 arr배열 인덱스로 넣어 그 값에 해당하는 방법의 수를 출력한다.

5. 소스코드

#include <iostream>
using namespace std;
int main(){
    int T; //테스트 케이스 개수
    cin>>T; //테스트 케이스 개수 입력
    int* testcase = new int[T]; //테스트 케이스 개수만큼 배열 할당
    int arr[12] = {0, }; //방법의 수를 저장해 놓을 배열

    for(int i = 0; i < T; i++){ //테스트 케이스 각각 입력
        cin>>testcase[i];
    }

    arr[0] = 1; //계산의 편의를 위해 arr[0] = 1로 설정.
    for(int i = 1; i < 11; i++){
        if(i - 1 >= 0){
            arr[i] += arr[i - 1];
        }
        if(i - 2 >= 0){
            arr[i] += arr[i - 2];
        }
        if(i - 3 >= 0){
            arr[i] += arr[i - 3];
        }
    }

    for(int i = 0; i < T; i++){
        cout<<arr[testcase[i]]<<endl; //arr 배열에 저장해놓은 결과 출력
    }

    return 0;
}