성우리뷰
C++ 중첩 및 조합 이용, 덱에 숫자 넣어 최소한의 합 만들기
두원공대88학번뚜뚜
2021. 10. 28. 18:17
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>
#include <limits>
#include <iterator>
using namespace std;
//있는거 처리
vector<int> yes;
//없는거 넣은 벡터
vector<int> none;
//정답
vector<int> ans;
int pushret = 2100000000;
//count - 지금까지 몇개 넣음?
//many - 넣어야 하는 수
//put - 이전에 넣은 idx
int dfs(int count, int many, int put) {
if (many == count) {
vector<int> tmp = yes;
sort(tmp.begin(), tmp.end());
int ret = tmp[0];
for (int i = 1; i < tmp.size(); i++) {
if (tmp[i] == tmp[i - 1] + 1)
continue;
ret += tmp[i];
}
if (pushret > ret)
pushret = ret;
return ret;
}
for (int j = put+1; j < none.size(); j++) {
yes.push_back(none[j]);
int ret = dfs(count+1, many, j);
yes.pop_back();
}
}
void solve(int n, vector<int> deck) {
int size = n - deck.size();
int turn = 0;
for (int i = 1; i <= n; i++) {
if (turn < deck.size() && deck[turn] == i) {
yes.push_back(i);
turn++;
}
else {
none.push_back(i);
}
}
//총 size만큼 실행. 각 실행시마다
for (int i = 1; i <= none.size(); i++) {
pushret = 2100000000;
for (int j = 0; j < none.size(); j++) {
yes.push_back(none[j]);
int ret = dfs(1, i, j);
yes.pop_back();
}
ans.push_back(pushret);
cout << pushret << "\n";
}
return;
}
int main(void){
solve(16, { 1,2,6,9,10,13,15 });
return 0;
}