백준 9095 - 1,2,3 더하기

주어진 N값을 1, 2, 3을 이용해 조합할 수 있는 경우의 수를 구하는 프로그램입니다. DFS를 이용할 수 있습니다.

#include <iostream>
 
using namespace std;
 
int cnt = 0;
 
void dfs(int acc,int target, int add)
{
    if (acc + add > target)
        return;
    if (acc + add == target)
        cnt++;
    dfs(acc + add, target, 1);
    dfs(acc + add, target, 2);
    dfs(acc + add, target, 3);
    return;
}
 
int main()
{
    ios::sync_with_stdio;
    cin.tie(0);
    
    int TC;
    cin >> TC;
    for (int tc = 0; tc < TC; tc++)
    {
        int N;
        cin >> N;
 
        dfs(0,N, 1);
        dfs(0, N, 2);
        dfs(0, N, 3);
 
        cout << cnt <<"\n";
        cnt = 0;
    }
    
    return 0;
}

테스트 케이스의 수 TC를 입력받고, 그 횟수만큼 반복합니다. 각 테스트 케이스 때 마다 N을 입력받고, 1로 시작, 2로 시작, 3으로 시작을 모두 dfs의 시작으로 사용합니다.

각 DFS는 1, 2, 3을 더해보며 재귀하며, 더한 값이 목표 값을 넘으면 그냥 return, 같을 경우엔 카운트를 올림으로써 경우의 수를 셀 수 있습니다.