3개의 숫자를 더하여 술래가 원하는 숫자를 만드세요 - level 2

해결 방법

문제 자체가 어렵다기 보다는 예외 케이스가 많아서 힘들었다. 일단 이 문제 반례를 찾으시는 분은 아래 케이스를 해보길 바랍니다.

 input
 5 5 5 2 12
 12
 output
 2 5 5

전체 소스

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
ll num[30], cnt, T, n;
vector<vector<ll>> check;
ll sum(vector<ll> v) {
    ll ret = 0;
    for(int i = 0; i < v.size(); ++i)
        ret += v[i];
    return ret;
}
void dfs(vector<ll> v, int here, int c) {
    if(c == 3) {
        if(T == sum(v)) {
            for(int i = 0; i < check.size(); ++i) {
                int j = 0;
                for(; j < check[i].size(); ++j)
                    if(check[i][j] != v[j])
                        break;
                if(j == 3)
                    return;
            }
            cnt++;
            for(int i = 0; i < v.size() - 1; ++i)
                cout << v[i] << ' ';
            cout << v.back() << '\n';
            check.push_back(v);
        }
        return;
    } 
    for(int i = here+1; i < n; ++i) {
        v.push_back(num[i]);
        dfs(v, i, c+1);
        v.pop_back();
    }
}
int main() {
    do {
        cin >> num[n];
        n++;
    } while(getchar() != '\n');
    cin >> T;
    sort(num, num + n);
    dfs(vector<ll>(),-1,0);
    if(cnt == 0)
        cout << "NO";
    return 0;
}

[출처] https://level.goorm.io/exam/43060/3%EA%B0%9C%EC%9D%98-%EC%88%AB%EC%9E%90%EB%A5%BC-%EB%8D%94%ED%95%98%EC%97%AC-%EC%88%A0%EB%9E%98%EA%B0%80-%EC%9B%90%ED%95%98%EB%8A%94-%EC%88%AB%EC%9E%90%EB%A5%BC-%EB%A7%8C%EB%93%9C%EC%84%B8%EC%9A%94/quiz/1