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

19942호:다이어트

N에서 몇 가지 재료를 선택하고 그 영양소(단백질, 탄수화물, 지방, 비타민)가 일정 수준 이상이어야 합니다. 아래 표에 나열된 여섯 가지 재료 중 하나를 선택하고

www.acmicpc.net

흐름

잘못된 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> info(15); //재료 정보 저장
int n, p,f,s,v,mp,mf,ms,mv, price, ret_price=987654321;
vector<int> answerlist;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    cin >> mp >> mf >> ms >> mv;
    for(int i=0;i<n;i++){
        cin >> p >> f >> s >> v>> price;
        info(i).push_back(p);
        info(i).push_back(f);
        info(i).push_back(s);
        info(i).push_back(v);
        info(i).push_back(price);
    }
    //2. 비트마스킹 수행
    for(int i=0;i<(1<<n);i++){ //경우의 수
        p=f=s=v=price=0;
        vector<int> temp;
        for(int j=0;j<n;j++){ //몇번째 자리마다
            if(i & (1<<j)){ //재료 존재하면 단지탄비,가격 더하고 재료번호 저장
                p += info(j)(0);
                f += info(j)(1);
                s += info(j)(2);
                v += info(j)(3); 
                price += info(j)(4);
                temp.push_back(j);
            }
        }
        if(p>=mp && f >=mf && s >=ms && v >=mv){ //최소 영양성분 넘으면
                if(ret_price != price){ //같은 가격이라면 이미 사전순으로 빠른게 저장되어있으므로 pass, 그렇지않을때 비교하기
                    ret_price = min(ret_price, price); //최소비용인지 확인하고
                    if(ret_price == price){ //최소비용이면 재료 리스트 저장
                        answerlist = temp;
                    } 
                } 
            }
    }
    //3. 정답 출력
    if(ret_price==987654321) cout << "-1\n"; //정답 존재하지않을경우
    else {
        cout << ret_price <<"\n"; //가격
        for(int e:answerlist) cout << e+1 << " "; //재료번호, 1부터 시작
    }
    return 0;
}

가나다순으로 출력되는 부분이 잘못된 것 같습니다.

가장 먼저 저장한 것이 알파벳순으로도 가장 빠른 줄 알았는데 그렇지 않았습니다.

https://www.acmicpc.net/board/view/57208

기사 읽기 – 제가 뭔가 잘못하고 있는 건가요?

댓글을 달려면 로그인이 필요합니다.

www.acmicpc.net

여기에서 검색

정답은 0 3번인데 정답도 3번째 재료에 만족하기 때문에 나중에는 저장하지 않습니다.

그런데 정답은 1,2,3인데, 알파벳 순서(?)로는 {1,2,3}이 3보다 빠르기 때문인 것 같습니다.

알파벳 판

출력은 알파벳순입니다. 정렬 기준 순서의 첫 번째 항목을 출력하는 것과 같습니다.

벡터 값을 저장하고 정렬해 보겠습니다.

올바른 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> info(15); //재료 정보 저장
int n, p,f,s,v,mp,mf,ms,mv, price, ret_price=987654321;
vector<vector<int>> answerlist;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    cin >> mp >> mf >> ms >> mv;
    for(int i=0;i<n;i++){
        cin >> p >> f >> s >> v>> price;
        info(i).push_back(p);
        info(i).push_back(f);
        info(i).push_back(s);
        info(i).push_back(v);
        info(i).push_back(price);
    }
    //2. 비트마스킹 수행
    for(int i=0;i<(1<<n);i++){ //경우의 수
        p=f=s=v=price=0;
        vector<int> temp;
        for(int j=0;j<n;j++){ //몇번째 자리마다
            if(i & (1<<j)){ //재료 존재하면 단지탄비,가격 더하고 재료번호 저장
                p += info(j)(0);
                f += info(j)(1);
                s += info(j)(2);
                v += info(j)(3); 
                price += info(j)(4);
                temp.push_back(j);
            }
        }
        if(p>=mp && f>=mf && s >=ms && v >=mv){ //최소 영양성분 넘고
            if(ret_price != price){ //비용이 같지않을때
                ret_price = min(ret_price,price); //최소비용인지 확인하고
                if(price == ret_price){ //최소비용일 경우
                    while(!answerlist.empty()) answerlist.pop_back(); //answerlist 클리어
                    answerlist.push_back(temp);
                }
            }
            else if (ret_price == price){ //같은 최소비용일때
                answerlist.push_back(temp);
            }
        }
    }
    //3. 정답 출력
    if(ret_price==987654321) cout << "-1\n"; //정답 존재하지않을경우
    else {
        cout << ret_price <<"\n"; //가격
        sort(answerlist.begin(), answerlist.end());
        for(int e:answerlist(0)) cout << e+1 << " "; //재료번호, 1부터 시작
    }
    return 0;
}

벡터 저장 벡터꽤 많이 사용하는 것 같다. 기억하자