[C++] 백준(BOJ) - 19942 : 다이어트
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
알고리즘
- 브루트포스
- 백트래킹
- 비트마스킹
풀이
- $2^{32}$ 미만의 경우의 수 같은 경우 비트마스킹을 이용하여 모든 경우의 수를 표현 할 수 있다
- 예시 코드
int n = 4; for(int i = 0; i < (1 << n); i++) // 모든 경우의 수에 대해 확인 i 0000 0001 0010 ... { for(int j= 0; j < n; j++) // j가 0번째 인덱스 부터 돌아가며 확인 { if(i & (1 << j)) // i와 j번째 인덱스의 비트가 켜져있는가? (존재) { go(); // 함수 실행 } } }
- 조합의 모든 경우의 수를 한번의 for문으로 표현 가능
- 위의 경우 : $4C0$ + $4C1$ + $4C2$ + $4C3$+ $4C4$
- 모든 경우의 수를 기반으로 로직을 짜야할 때 유용하다
코드
// BOJ-19942 : 다이어트
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int n, mp, mf, ms, mv;
int p, f, s, v, res = INF, sum;
struct A{
int mp, mf, ms, mv, cost;
}a[16];
map<int, vector<vector<int>>> res_v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> 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;
}
for (int i = 0; i < (1 << n); i++) // 모든 경우의 수 탐색 (2의 n승 개의 가지수)
{
p = f = s = v = sum = 0;
vector<int> vec; // 재료의 인덱스를 담을 임시 벡터
for (int j = 0; j < n; j++)
{
if (i & (1 << j)) // 해당 인덱스에 비트가 켜져있다면 해당 재료가 있다는 것
{
vec.push_back(j + 1); // 재료의 번호는 1번부터 시작이기 떄문에 (j+1) 값을 임시벡터 vec에 삽입
p += a[j].mp;
f += a[j].mf;
s += a[j].ms;
v += a[j].mv;
sum += a[j].cost;
}
}
if (p >= mp && f >= mf && s >= ms && v >= mv) // 최소 영양소 기준을 만족했다면
{
if (res >= sum) // 현재 최소값 res보다 위에서 계산한 sum 값이 작다면
{
res = sum; // res 값 현재 sum값으로 초기화하고
res_v[res].push_back(vec); // res key 값에 vec(재료 번호를 담고있음)를 push_back
}
}
}
if (res == INF) cout << -1 << '\n'; // res 값이 변화가 없었다면 조건에 만족하는 조합 없음
else
{
sort(res_v[res].begin(), res_v[res].end()); // 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것 출력
cout << res << '\n';
for (int a : res_v[res][0]) cout << a << ' ';
}
return 0;
}
평가
- 모든 조합의 경우의 수의 합을 구할 때 비트마스킹을 이용해 구할 수 있다
- 간단한 구조체를 이용해 입력값들을 분류 및 저장 할 수 있다
- 문제에서 필요한 자료구조 형을 상황에 맞춰 유연하게 사용하는 연습을 한다
