[알고리즘] 백준 19942

백준 19942번 다이어트

해결 과정 요약

각각의 식재료를 먹는 것과 먹지 않는 것 그 모든 경우의 수를 다 확인해줘야 한다.
이런 문제는 비트마스킹을 사용하면 쉽게 풀 수 있다.

    for(int i=1; i<(1 << N); i++){
        for(int j=0; j<N; j++){
            if(i & (1 << j)){
                ...
            }
        }
        ...
    }

위와 같이 비트 연산자와 if문을 이용하면 모든 경우의 수에 대해 먹을 식재료를 알 수 있다.
그리고 최소비용이 중복된다면 사전순으로 가장 앞서는 것을 출력하는 것이 문제의 요구이다.
따라서 식재료를 string으로 저장해서 map의 value로(key는 비용) 넣어주고

if(account[0] >= mp && account[1] >= mf 
&& account[2] >= ms && account[3] >= mv){
    if(m.find(account[4]) == m.end() || m[account[4]] > s)
    	m[account[4]] = s;
    }

위와 같이 조건문을 걸어주면 사전순으로 가장 앞서는 최소비용이 map의 가장 첫번째 인덱스에 담기게 된다.

풀이

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

int N,mp,mf,ms,mv;
int t[16][5];
map<int,string> m;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> mp >> mf >> ms >> mv;
    for(int i=0; i<N; i++){
        cin >> t[i][0] >> t[i][1] >> t[i][2] >> t[i][3] >> t[i][4];
    }
    for(int i=1; i<(1 << N); i++){
        int account[5] = {0,};
        string s = "";
        for(int j=0; j<N; j++){
            if(i & (1 << j)){
                s += to_string(j+1); s += " ";
                for(int k=0; k<5; k++)
                    account[k] += t[j][k];
            }
        }
        if(account[0] >= mp && account[1] >= mf 
        && account[2] >= ms && account[3] >= mv){
            if(m.find(account[4]) == m.end() || m[account[4]] > s)
                m[account[4]] = s;
        }
    }
    if(m.size() == 0){
        cout << -1;
        return 0;
    }
    auto e = m.begin();
    cout << e->first << "\n";
    cout << e->second;
    
    return 0;
}

코멘트

최소비용을 구하는 것은 쉽지만 사전순이라는 조건때문에 고민이 많아졌던 문제