성우리뷰

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;
 }