[SWEA 4747] 사막에서 만난 지니

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWSNnKiazq0DFAUr

#include <iostream>

#include <vector>

#include <algorithm>

#include <memory.h>

using namespace std;

int N, result, sum, s1, s2, s3, flag, t;

vector <int>arr;

vector <int> v[2];

void cal(int count, int sss, int start)

{

if (flag == 1) return;

if (count == 3)

{

cout << "#" << t << endl;

for (int i = 0;i < v[0].size();i++)

{

cout << v[0][i];

if (i == v[0].size() - 1) cout << endl;

else cout << " ";

}

for (int i = 0;i < v[1].size();i++)

{

cout << v[1][i];

if (i == v[1].size() - 1) cout << endl;

else cout << " ";

}

for (int i = 0;i < arr.size();i++)

{

cout << arr[i];

if (i == arr.size() - 1) cout << endl;

else cout << " ";

}

flag = 1;

}

if (sss == sum)

{

cal(count + 1, 0, 0);

}

for (int i = start; i < arr.size(); i++)

{

if (flag == 1) return;

if (sss + arr[i] > sum) return;

int tmp = arr[i];

v[count - 1].push_back(tmp); arr.erase(arr.begin()+i);

cal(count, sss + tmp, i);

v[count - 1].pop_back(); arr.insert(arr.begin()+i, tmp);

}

}

int main()

{

int T;

cin >> T; t = 1;

while (T--)

{

cin >> N; sum = 0; s1 = 0;s2 = 0;s3 = 0; flag = 0; int a;

for (int i = 0; i < N; i++) { cin >> a; arr.push_back(a); sum += a; } sum /= 3;

cal(1, 0, 0);

t++;

v[0].clear();v[1].clear(); arr.clear();

}

return 0;

}