[백준 9095번] 1, 2, 3 더하기 (C/C++)

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

9095번: 1, 2, 3 더하기

---

1, 2, 3 더하기 문제는 백트래킹 또는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. th번째에서 1, 2, 3 중에 선택하고, th + 1번째를 선택하도록 하면 됩니다.

 

아래는 백트래킹을 이용한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int selected[11];

int n, m, ans = 0;
void back(int th){
    int s = 0;
    for(int i = 0; i < th - 1; i++) s += selected[i];   // 현재까지 선택한 수를 합함
    
    if(s == m){ // 선택된 수가 m인 경우 방법 + 1
        ans++;
    }else if(s < m){    // 더 선택할 수 있는 경우
        for(int i = 1; i <= 3; i++){    // 1, 2, 3 중에 선택
            selected[th - 1] = i;
            back(th + 1);   // th + 1번째 수 선택
        }
    }
}

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

    cin >> n;
    while(n--){
        cin >> m;
        ans = 0;
        back(1);    // th번째부터 선택하여 m을 만드는 백트래킹을 수행
        cout << ans << "\n";
    }
}

다이나믹 프로그래밍을 이용하면 1, 2, 3 더하기 문제를 더 간단하게 풀 수 있습니다.

N을 1로 만드려면 (N - 1)을 1로 만드는 각 경우의 수에 1을 더해주면 N을 만들 수 있습니다. 마찬가지로 (N - 2)를 1로 만드는 각 경우의 수에 2를 더해주면 N을 만들 수 있습니다. 따라서 d[N]을 N을 1로 만드는 경우의 수라고 했을 때 점화식은 아래와 같습니다.

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

 

아래는 다이나믹 프로그래밍을 이용한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int d[11];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;

    d[1] = 1; d[2] = 2; d[3] = 4; 
    for(int i = 4; i <= 11; i++) d[i] = d[i - 1] + d[i - 2] + d[i - 3];

    while(t--){
        int c; cin >> c;
        cout << d[c] << "\n";
    }
}