[9095번] 1,2,3 더하기

9095번: 1, 2, 3 더하기

 

www.acmicpc.net

이 문제는 재귀를 이용해서 풀 수도 있고, DP를 이용해서 풀 수도 있다.

입력 값이 적기 때문에 재귀를 이용해도 충분히 풀 수 있다.

/*9095번 1,2,3 더하기*/
#include <iostream>
using namespace std;
int T, input, result;

void go(int sum) {
    if (sum > input) return;
    else if (sum == input) result++;
    else {
        for (int i = 1; i <= 3; i++) {
            int temp = sum;
            temp += i;
            go(temp);
        }
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> input;
        go(0);
        cout << result << '\n';
        result = 0;
    }
}

DP로 풀 경우, 예를 들어 입력값이 4이면

4를 만들기 위해서 3을 만드는 방법의 수를 찾아야하고,

3을 만들기 위해선 2를 만드는 방법의 수를 찾아야하고,

2를 만들기 위해선 1을 만드는 방법의 수를 찾아야한다.

이렇게 바텀업 방식으로 방법의 수를 배열에 저장시켜 푼다.

/*9095번 1,2,3 더하기 (DP)*/
#include <iostream>
using namespace std;
int T, input;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        int Memo[12] = {};
        Memo[0] = 1;
        cin >> input;
        for (int i = 1; i <= input; i++) {
            if (i - 1 >= 0)    Memo[i] += Memo[i - 1];
            if (i - 2 >= 0)    Memo[i] += Memo[i - 2];
            if (i - 3 >= 0)    Memo[i] += Memo[i - 3];
        }
        cout << Memo[input] << '\n';
    }
}