[비트마스킹][브루트 포스] 19942 다이어트 c++구현

목차

https://www.acmicpc.net/problem/19942

문제

 

 

참고

https://be-senior-developer.tistory.com/134

[비트 마스킹][c++] 개념과 활용 방법에 대해서 알아보자

 

문제 구현 방향

N의 범위가 31이하이고 모든 조합을 구해보는 것이므로 비트마스킹을 적용해볼 수 있다.

모든 조합을 만들어서 하는 것은 비효율적이기 때문에 비트마스킹을 이용했다.

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

vector<int> v[10];

int minTotal = 99999;  //최소를 구하는 것이므로 큰 수를 초기값으로 한다.
vector<int> ans;  //정답 배열
int N;
int standA, standB, standC, standD;  //기준 값

//비트 마스킹을 이용한 모든 조합 탐색
void combi() {

    for (int i = 0; i < (1 << N); i++) {
        int cA = 0, cB = 0, cC = 0, cD = 0, cE = 0;
        vector<int> num;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                cA += v[j][0];
                cB += v[j][1];
                cC += v[j][2];
                cD += v[j][3];
                cE += v[j][4];
                num.push_back(j);
            }
        }
        if (cA >= standA && cB >= standB && cC >= standC && cD >=standD ) {
            if (cE < minTotal) {
                ans.clear();
                for (auto k : num)
                    ans.push_back(k);
                minTotal = cE;
            }
            // 비용이 같을 경우 사전 순이기 때문에 조건을 추가했다.
            else if (cE == minTotal) {
                string a, b;
                for (auto k : num)
                    a += to_string(k);
                for (auto k : ans)
                    b += to_string(k);
                if (a < b) {
                    ans.clear();
                    for (auto k : num)
                        ans.push_back(k);
                    minTotal = cE;
                }

            }
        }
    }
}

int main() {
    int a, b, c, d, e;

    cin >> N;
    cin >> standA >> standB >> standC >> standD;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c >> d >> e;
        v[i].push_back(a);
        v[i].push_back(b);
        v[i].push_back(c);
        v[i].push_back(d);
        v[i].push_back(e);
    }
    combi();
    //조합이 없을 경우 -1
    if (minTotal == 99999)
    {
        cout << -1;
        return 0 ;
    }
    else
    {
        cout << minTotal << "\n";
		//오름차순 정렬
        sort(ans.begin(), ans.end());
        for (auto k : ans)
            cout << k+1 << " ";
    }
    return 0;
}