[백준] 9095번: 1, 2, 3 더하기 - C++

문제

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

 

---

DP를 이용하여 푸는 문제. 앞서 풀었던 타일링 문제들과 동일하게 생각하면 쉽게 풀 수 있다.

1, 2, 3만으로 숫자 n을 만들기 위한 경우의 수는 다음과 같다.

1. (n - 1)에 1을 더하는 경우

2. (n - 2)에 2를 더하는 경우

3. (n - 3)에 3을 더하는 경우

D[n]은 n을 1, 2, 3의 합으로 나타내는 방법의 수라고 할 때, 위의 세 방법을 고려하여 점화식을 세우면 다음과 같다.

 

D[n] = D[n - 1] + D[n - 2] + D[n - 3]

 

문제는 top-down 방식으로 풀었다.

 

코드

#include <cstdio>
#include <vector>
#define MAX 12

using namespace std;

vector<int> memo(MAX, 0);
int DP(int num);

int main(void) {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        printf("%d\n", DP(num));
    }
    return 0;
}

int DP(int num) {
    if(num == 0) return 1;
    if(num < 3) return num;
    if(memo[num] > 0) return memo[num];

    int result = (DP(num - 1) + DP(num - 2) + DP(num - 3));
    memo[num] = result;
    return result;
}