[C/C++] BOJ 12101 :: 1, 2, 3 더하기 2

 BOJ 12101 :: 1, 2, 3 더하기 2

문제 링크 : https://www.acmicpc.net/problem/12101

푸는 방법이 여러 가지가 있을 수 있는 것 같은데 나는 BACKTRACKING 방법으로 풀었다!

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_12101/BOJ_12101.cpp

#include<iostream>
using namespace std;
 
int n, k;
int ans[10];
int cnt;
bool flag = true;
 
void answer(int _idx)
{
    int i;
    for (i = 0; i < _idx-1; i++)
    {
        cout << ans[i] << '+';
    }
    cout << ans[i];
    return;
}
 
void dfs(int _idx, int _sum)
{
    if (!flag || _sum > n) return;
    if (n == _sum)
    {
        cnt++;
        if (cnt == k) {
            flag = 0;
            answer(_idx);
        }
        return;
    }
    for (int i = 1; i <= 3; i++)
    {
        ans[_idx] = i;
        dfs(_idx+1, _sum+i);
    }
}
int main(void)
{
    cin >> n >> k;
    
    int idx = 0;
    int length = 0;
 
    for (int i = 1; i <= 3; i++)
    {
        ans[idx] = i;
        dfs(idx+1, i);
    }
 
    if (flag) cout << -1;
 
    return 0;
}