다이어트( BOJ 19942 )

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

19942번: 다이어트

 

문제 파악하기

제시된 영양분을 만족할 수 있도록 식자료를 선택하되, 비용이 가장 작아지는 방법을 찾는 문제입니다. 식자료의 개수(N)이 최대 15개 입력되기 때문에 모든 경우의 수를 탐색하는 방법을 사용할 수 있습니다.

 

문제 해결하기

우선, 식재료를 선택할 수 있는 모든 경우의 수를 탐색합니다. 여러 가지 방법이 있지만 가장 직관적인 방법은 함수를 사용하는 방법이라고 생각합니다. 함수를 다음과 같이 선언해봅시다.

sv(int idx, vector< int > s) >> idx: 현재 사용할 식재료 / s: 지금까지 사용한 식재료

 

s에 idx에 해당하는 식재료를 넣어서 탐색하고, 넣지 않고 탐색하면 N개의 식재료를 가지고 나올 수 있는 모든 경우를 탐색할 수 있습니다. 그리고 가장 중요한 건 마지막 종료 조건입니다. idx가 식재료의 개수(N)를 넘어가면 우리는 현재까지 선택한 식재료를 가지고 2가지 조건을 만족하는지 살펴볼 것입니다. 첫 번째, 제시된 영양분을 만족할 수 있는가 입니다. s에 저장된 인덱스를 사용해서 선택한 식재료를 사용하여 제시된 영양분을 만족하는지 확인해야 합니다. 두 번째, 비용과 사용된 식재료의 사전적 순서가 가장 빠른가 입니다. 만약 비용이 더 작다면 무조건 s의 값이 정답에 가깝기 때문에 그대로 사용해야 합니다. 비용이 같은 경우 또한 확인이 필요합니다. 비용이 같은 경우에는 사전적 순서를 확인해야 합니다. 사전적 순서를 사용하지 않으면 비용이 0인 경우(참고)를 제대로 구분하지 못 하기 때문입니다. 2가지를 모두 확인한 다음에 결괏값을 확인하면 우리가 원하는 결과를 얻을 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#define VMAX 5
#define MAX 987654321
using namespace std;
 
struct INP {
    int val[VMAX];
 
    void init() { for(int i=0;i<VMAX;i++) val[i] = 0; }
    INP operator+ (INP t) {
        INP ret;
        for(int i=0;i<VMAX;i++) ret.val[i] = val[i] + t.val[i];
 
        return ret;
    }
};
 
int N, m[VMAX];
int p, f, s, v, c;
vector< INP > inp;
 
int totCost;
vector< int > tmp, sel;
 
bool isSatisfy(INP t) {
    for(int i=0;i<VMAX-1;i++) {
        if(t.val[i] < m[i]) return 0;
    }
 
    return 1;
}
 
bool isSmall(vector< int > a, vector< int > b) {
    if(b.empty()) return 1;
    else {
        for(int i=0;i<a.size() and i<b.size();i++) {
            if(a[i] == b[i]) continue;
            else return a[i] < b[i];
        }
 
        return a.size() < b.size();
    }
}
 
void sv(int idx, vector< int > s) {
    if(idx == N) {
        INP t;
 
        t.init();
        for(int idx:s) t = t+inp[idx];
 
 
        if(isSatisfy(t) and t.val[4] <= totCost) {
            if( (t.val[4] < totCost) or (t.val[4] == totCost and isSmall(s, sel)) ) {
                totCost = t.val[4];
                sel = s;
            }
        }
 
        return;
    }
 
    s.push_back(idx);
    sv(idx+1, s);
 
    s.pop_back();
    sv(idx+1, s);
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=0;i<VMAX-1;i++) scanf("%d", &m[i]);
    for(int i=0;i<N;i++) {
        scanf("%d %d %d %d %d", &p, &f, &s, &v, &c);
        inp.push_back({p, f, s, v, c});
    }
 
    // 탐색
    totCost = MAX;
    sv(0, tmp);
 
    // 출력
    if(totCost == MAX) printf("-1");
    else {
        printf("%d\n", totCost);
        for(int val:sel) printf("%d ", val+1);
    }
}

후기

기본적인 브루트포스 문제라고 생각합니다. 만약 최소 비용만 구하는 문제라면 브루트포스 기초 문제로 적절하지만 순서를 저장하거나 사전적 순서를 확인해야 하기에 브루트포스 연습 문제로 적절하다고 생각합니다.