이번에는 백준 19942번 다이어트 문제를 풀어보았습니다.
문제를 처음 봤을 때 식재료를 선택하는 모든 경우를 확인해야 한다고 생각했습니다.
식재료의 개수가 최대 15개이기 때문에 모든 부분집합을 비트마스킹으로 탐색해도 충분하다고 판단하였습니다.
각 부분집합마다 영양소와 비용을 계산한 뒤, 조건을 만족하는 경우 최소 비용과 선택한 식재료를 갱신하도록 구현하였습니다.
문제 설명
각 식재료에는 단백질, 지방, 탄수화물, 비타민, 가격이 주어집니다.
주어진 최소 영양소 조건을 모두 만족하면서 가격의 합이 가장 작은 식재료의 조합을 구해야 합니다.
가격이 같은 경우에는 식재료 번호가 사전순으로 앞서는 경우를 출력해야 합니다.
풀이 아이디어
비트마스킹을 이용하여 모든 부분집합을 탐색하였습니다.
하나의 비트는 하나의 식재료를 의미하도록 하였습니다.
현재 부분집합에 포함된 식재료들의 영양소와 가격을 모두 더한 뒤 최소 영양소 조건을 만족하는지 확인하였습니다.
조건을 만족하는 경우에는 최소 비용과 비교하여 갱신하였습니다.
만약 비용이 같은 경우에는 비트마스크를 비교하여 사전순으로 앞서는 경우를 선택하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> ret(5);
int ret_bit =0;
vector<vector<int>> inp;
int m[4];
int n;
bool check_valid(vector<int> temp) {
for (int i = 0; i < 4; i++) {
if (temp[i] < m[i])
return false;
}
return true;
}
bool bitcmp(int a, int b) {
for (int i=0; i<n; i++) {
if (a & (1 << i) && !(b & (1 << i)))
return true;
else if (!(a & (1 << i)) && b & (1 << i))
return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ret[4] = INT_MAX;
cin >> n;
for (int i=0; i<4; i++) {
cin >> m[i];
}
for (int i=0; i<n; i++) {
inp.push_back(vector<int>());
for (int j=0; j<5; j++) {
int tmp;
cin >> tmp;
inp[i].push_back(tmp);
}
}
for (int i=0; i<(1 << n); i++) {
vector<int> tmp(5,0);
for (int j=0; j<n; j++) {
if (i & (1 << j)) {
for (int k=0; k<5; k++)
tmp[k] += inp[j][k];
}
}
if (check_valid(tmp)) {
if (ret[4] > tmp[4]) {
ret = tmp;
ret_bit = i;
}
else if (ret[4] == tmp[4] && bitcmp(i, ret_bit)) {
ret = tmp;
ret_bit = i;
}
}
}
if (ret[4] == INT_MAX) {
cout << -1 << '\n';
}
else {
cout << ret[4] << '\n';
for (int i=0; i<n; i++) {
if (ret_bit & (1 << i))
cout << i + 1 << ' ';
}
}
return 0;
}풀이 흐름
- 최소 영양소 조건을 입력받습니다.
- 각 식재료의 정보를 저장합니다.
- 비트마스킹을 이용하여 모든 부분집합을 탐색합니다.
- 선택된 식재료들의 영양소와 가격을 계산합니다.
- 최소 영양소 조건을 만족하는지 확인합니다.
- 최소 비용과 비교하여 정답을 갱신합니다.
- 비용이 같은 경우에는 사전순으로 앞서는 조합을 선택합니다.
- 탐색이 끝난 뒤 결과를 출력합니다.
구현 포인트
1. 비트마스킹을 이용한 부분집합 탐색
모든 식재료 선택 경우를 비트마스킹으로 탐색하였습니다.
for (int i=0; i<(1 << n); i++)각 비트가 하나의 식재료를 의미하도록 구현하였습니다.
if (i & (1 << j))현재 부분집합에 포함된 식재료만 선택하여 계산하였습니다.
2. 영양소 및 가격 계산
선택된 식재료들의 영양소와 가격을 모두 더하였습니다.
for (int k=0; k<5; k++)
tmp[k] += inp[j][k];tmp에는
- 단백질
- 지방
- 탄수화물
- 비타민
- 가격
이 순서대로 저장됩니다.
3. 최소 영양소 확인
현재 부분집합이 조건을 만족하는지 확인하였습니다.
if (check_valid(tmp))각 영양소가 최소 기준 이상인지 검사하도록 구현하였습니다.
if (temp[i] < m[i])
return false;4. 최소 비용 갱신
조건을 만족하면 현재 최소 비용과 비교하였습니다.
if (ret[4] > tmp[4]) {
ret = tmp;
ret_bit = i;
}더 작은 비용이라면 현재 조합으로 갱신하였습니다.
5. 비용이 같은 경우 처리
비용이 같은 경우에는 비트마스크를 비교하여 사전순으로 앞서는 조합을 선택하였습니다.
else if (ret[4] == tmp[4] && bitcmp(i, ret_bit)) {
ret = tmp;
ret_bit = i;
}bitcmp 함수에서 두 비트마스크를 비교하여 더 앞서는 조합을 선택하도록 구현하였습니다.
6. 선택한 식재료 출력
최종적으로 선택된 비트마스크를 이용하여 식재료 번호를 출력하였습니다.
for (int i=0; i<n; i++) {
if (ret_bit & (1 << i))
cout << i + 1 << ' ';
}비트가 켜져 있는 식재료만 출력하도록 구현하였습니다.
