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

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

풀이

합이 n이 되도록 1, 2, 3을 중복을 허용하고 순서를 고려하여 뽑는 경우의 수를 구해야 하므로 백트래킹 방법으로 풀었다.

현재 1, 2, 3 중 어떤 수 x를 선택하였을 때, 그 다음에 오는 수들의 합은 (n - x)이다.
이를 이용해서 (n - x) == 0인 시점에 답의 개수를 +1하였다.

코드

#include <iostream>
using namespace std;

int ans;

void backtracking(int x) {
    if(x == 0) {
        ans++;
        return;
    }
    for(int i=1; i<4; i++) {
        if(x < i) continue;
        backtracking(x-i);
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        
        ans=0;
        for(int i=1; i<4; i++) {
            backtracking(n-i);
        }
        
        cout << ans << "\n";
    }

    return 0;
}