19942번: 다이어트

다이어트

 

시간 제한                 메모리 제한                 제출                 정답                 맞힌 사람                 정답 비율

 

2 초

512 MB

6585

1658

1211

26.482%

문제

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해 보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

 

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

 

예제 입력 1 복사

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

예제 출력 1 복사

134
2 4 6

 

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

19942번: 다이어트

 

흐름

 

틀린 코드(사전순 출력 부분 틀림)

#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

글 읽기 - 제가 잘못하고 있는 부분이 있을까요?

여길 보면

내 코드의 답은 0 3 이 나오는데, 3번째 재료만 가져도 정답을 만족하기 때문에 그 뒤로는 저장하지 않는다.

정답 코드의 답은 0 1,2,3인데 1,2,3도 최소 비용을 만족하면서 3보다 {1,2,3}이 사전순으로 더 빠르기 때문이다.

 

사전순 출력

사전순 출력이란 결과값들을 sort 하여 맨 처음 원소부터 차례대로 출력하는 것과 같다.

벡터 값들을 저장하여 sort 하자.

 

맞은 코드

#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;
}

 

벡터를 저장하는 벡터가 꽤 많이 쓰이는 것 같다. 기억해 두자

 

선생님 코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
int n, mp,mf,ms,mv,b,c,d,e,sum, ret=INF;
struct A{
    int mp,mf,ms,mv, cost;
}a[16];
map<int, vector<vector<int>>> ret_v;

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 >> a[i].mp >> a[i].mf >> a[i].ms >> a[i].mv >> a[i].cost;
    }
    //2. 비트마스킹
    for(int i=1;i<(1<<n);i++){
        b=c=d=e=sum=0;
        vector<int> v;
        for(int j=0;j<n;j++){
            if(i & (1<<j)){
                v.push_back(j+1);//재로 번호 저장
                b += a[j].mp;
                c += a[j].mf;
                d += a[j].ms;
                e += a[j].mv;
                sum += a[j].cost;
            }
        }
        if(b>= mp && c >=mf && d>=ms && e>=mv){
            if(ret>=sum){
                ret=sum;
                ret_v[ret].push_back(v); //값에 따라 재료 번호 벡터 저장
            }
        }
    }
    //3. 정답 출력
    if(ret==INF) cout << -1 <<"\n";
    else{
        sort(ret_v[ret].begin(), ret_v[ret].end()); //최종 값에 대해 재료 번호 벡터 정렬
        cout << ret << "\n";
        for(int a:ret_v[ret][0]){ //사전순으로 맨 처음 벡터 출력
            cout << a << " ";
        }
    }
    return 0;
}

 

• 구조체를 정의하여 변수들을 묶었다.
• map<int, vector<int>>> ret_v; 를 이용하여 ret값에 대한 벡터들을 저장하였다.

 

정리해본 코드

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

const int INF = 987654321;
int n,mp,mf,ms,mv,r1,r2,r3,r4,total_price, ret=INF;
struct A{
    int p,f,s,v,c;
} a[15];
map<int, vector<vector<int>>> m;

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 >> a[i].p >> a[i].f >> a[i].s >> a[i].v >> a[i].c;
    }
    //2. 비트마스킹 수행
    for(int i=1;i<(1<<n);i++){
        r1=r2=r3=r4=total_price=0;
        vector<int> temp;
        for(int j=0;j<n;j++){ //재료 존재하는지 확인
            if(i & (1<<j)){
                temp.push_back(j+1); //재료번호 저장
                r1 += a[j].p;
                r2 += a[j].f;
                r3 += a[j].s;
                r4 += a[j].v;
                total_price += a[j].c;
            }
        }
        if(r1 >= mp && r2>=mf && r3>=ms && r4>=mv){ //최소 영양성분 만족하면
            if(ret>=total_price){ //최소 비용이라면
                ret = total_price;
                m[ret].push_back(temp);
            }
        }
    }
    //3. 정답 출력
    if(ret==INF) cout << -1 << "\n";
    else {
        sort(m[ret].begin(), m[ret].end()); //사전순으로 정렬
        cout << ret << "\n";
        for(int e: m[ret][0]) cout << e << " ";
    }
}