1, 2, 3 더하기 2 12101

문제

접근 방법

1, 2, 3을 순차적으로 더해가며 DFS를 하면 해결될 것이다.

코드

#include <iostream>
#include <string>
using namespace std;
int idx = 0, n, k;
string ret;
int dx[] = {1, 2, 3};
void dfs(int sum, string exp)
{
    if (sum == n)
    {
        ++idx;
        if (idx == k)
        {
            cout << exp;
            exit(0);
        }
    }
    for (int i = 0; i < 3; ++i)
    {
        int nextSum = sum + dx[i];
        if (nextSum <= n)
        {
            string nextExp = exp + to_string(dx[i]) + (nextSum < n ? "+" : "");
            dfs(nextSum, nextExp);
        }
    }
}
int main()
{
    cin >> n >> k;
    dfs(0, "");
    cout << -1;
    return 0;
}

풀이

DFS를 활용하면 된다.
1, 2, 3을 차례대로 사용하여 재귀함수에 진입하고 n에 해당하는 값에 도달하면 몇 번째 수인지 갱신을 해준다. k번째 수에 해당하는 값이 되면 출력해주고 끝내주면 된다.
bool 형 변수로 확인하여 다른 재귀함수의 작동을 멈출 수도 있지만 exit를 활용하면 간단하게 해결된다는 점이 좋은 것 같다. 하지만 여러 개의 테스트케이스를 주는 문제일 경우 exit를 사용할 시 다른 테스트케이스를 무시할 수 있기에 이렇게 답을 하나만 출력하는 문제에서만 활용해야 한다.