[백준 19942] 다이어트

문제링크 : https://www.acmicpc.net/problem/19942

복기

1. 다른 방법으로 풀어 보려고 했는데 점점 이상해졌다.
2. 비트마스킹 기준, 정수 5가 정수 11보다 사전 정렬 시 더 뒤에 와야 한다. 이걸 못 깨달았다.

문제유형 : 조합 찾기

조합 전략 : bitmasking 

---

비트셋 프린트 :

void printBitSet(vector<pp> resultSetVector, int N){
    for(pp resultPair : resultSetVector ){
        for (int i = 0; i < N; i++){
            if (resultPair.first & (1 << i)){
                cout << i + 1 << " ";
            }
        }
    }
}

위의 방법으로 비트를 받아서 프린트 하면 사전 정렬이 힘들어진다. custum sorting으로 정렬해서 풀어보려고 했는데 너무 복잡하고 재귀까지 써서 하다 보니까 타임아웃 나서 주어진 해답으로 풀게 됐음.

//// 최소 bit를 리턴 
int getMinBit(int a){
    return a & (-a);
}

//// custom compare function : 최소 bit를 정수로 표현 해도 대소관계는 유지된다. 재귀버전 x
bool compare(pp a, pp b) {
    return getMinBit(a.first) < getMinBit(b.first);
}

최종 해답:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pp;
int N, mp, mf, ms, mv, res=INT_MAX;
map<int, vector<vector<int>>> resultSetVector;
struct food{
    int v[5];
};

vector<food> input(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> mp >> mf >> ms >> mv;
    vector<food> fList(N);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 5; j++){
            cin >> fList[i].v[j];
        }
    }
    return fList;
}

void solve(){
    vector<food> fList = input();
    for (int i = 0; i < (1 << fList.size()); i++){
        vector<int> v; 
        int sum[5] = {0};
        for (int j = 0; j < fList.size(); j++){
            if (i & (1 << j)){
                v.push_back(j+1); 
                for (int k = 0; k < 5; k++){
                    sum[k] += fList[j].v[k];
                }
            }
        }
        //// 1. 최소 영양소 조건 
        if (sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){   
            //2.2. 새로운 값으로 채워 줌. 
            //// 2. 최소 비용 
			if(res >= sum[4]){
				res = sum[4];
                resultSetVector[res].push_back(v); 
			}              
        }
    }
    
    if (res == INT_MAX) cout << -1 << '\n';
    else{
        sort(resultSetVector[res].begin(), resultSetVector[res].end());  
        cout << res << "\n";
		for(int a : resultSetVector[res][0]){
			cout << a << " ";
		} 
    }
}

int main(){
    solve();
}