인프런 커뮤니티 질문&답변

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
//// 다이어트 
int N,mp,mf,ms,mv; 
int resultSet;
vector<int> resultSetVector; 
typedef struct food{
    int v[5];  
}food; 

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

void printBitSet(int resultSet, int N){
    for(int i=0;i<N; i++){
        if( resultSet & (1<<i) ) {
            cout << i + 1 << " ";
        }
    }
}

//// logic 
// 1. 모든 조합을 구한다. 
// 2. 해당 조합 중에 최소 영양소 기준을 만족하는 조합을 찾는다. 
// 3. 해당 조합 중 최소 비용 조합을 찾는다.
void solve(){
    food* fList = input(); 
    int result = INT_MAX; 
    for(int i=0; i<(1<<N); i++){//O(N^2)
        //1.
        int sum[5] = {0};
        for(int j=0;j<N;j++){
            if(i&(1<<j)){
                sum[0] += fList[j].v[0];//pi
                sum[1] += fList[j].v[1];//fi
                sum[2] += fList[j].v[2];//si
                sum[3] += fList[j].v[3];//vi               
                sum[4] += fList[j].v[4];//ci    
            }    
        }
        //2.mp,mf,ms,mv 
        if(sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){
            //3.
            if(result >= sum[4]){
                result = sum[4];                  
                resultSet = i;//최소 비용 조합 
            }
        }
    }
    if(result == INT_MAX) cout << -1 << '\n';
    else{
        cout << result << "\n"; 
        printBitSet(resultSet, N); 
    }
}

int main(){
    solve(); 
}

void printBitSet(int resultSet, int N){
    for(int i=0;i<N; i++){
        if( resultSet & (1<<i) ) {
            cout << i + 1 << " ";
        }
    }
////.....

 //2.mp,mf,ms,mv 
        if(sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){
            //3.
            if(result >= sum[4]){
                result = sum[4];                  
                resultSet = i;//최소 비용 조합 
            }
        }

////..... 

if(result == INT_MAX) cout << -1 << '\n';
    else{
        cout << result << "\n"; 
        printBitSet(resultSet, N);//최소 비용 조합 출력 
    }}

안녕하세요 큰돌 님. 비트마스킹 문제 질문이 있어 여쭤봅니다. 어떤 반례가 있을지 궁금합니다.

• vector에 넣어주는 방식이 아니라, i 비트값을 업데이트 해서 프린트 해주는 방식으로 구현 했습니다.

• 위 방식만 다르기 때문에 여기서 문제가 있을 거라 추측됩니다.

• 12퍼센트 쯤에서 테케

  통과를 못 하더라구요ㅠ

   

  도와주시면 정말 감사드리겠습니다.

   

 공유 소스 보기 (acmicpc.net)