728x90
반응형
https://www.acmicpc.net/problem/19942
19942번: 다이어트
식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
struct Ingredient{
int p, f, s, v, c;
};
int n, mp, mf, ms, mv;
vector<Ingredient> v;
vector<int> tmp;
vector<int> ans;
int answer = 987654321;
void dfs(int idx, int sp, int sf, int ss, int sv, int sc){
if(sp >= mp && sf >= mf && ss >= ms && sv >= mv){
if(sc < answer || (sc == answer && ans > tmp)) {
answer = sc;
ans = tmp;
}
return;
}
if(idx == n + 1) return;
dfs(idx + 1, sp, sf, ss, sv, sc);
tmp.push_back(idx);
dfs(idx + 1, sp + v[idx].p, sf + v[idx].f, ss + v[idx].s, sv + v[idx].v, sc + v[idx].c);
tmp.pop_back();
}
int main() {
cin >> n >> mp >> mf >> ms >> mv;
v.push_back({0, 0, 0, 0, 0});
for(int i = 0; i < n; i++){
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
v.push_back({a, b, c, d, e});
}
dfs(1, 0, 0, 0, 0, 0);
if(answer == 987654321) cout << -1;
else {
cout << answer << endl;
for(int i = 0; i < ans.size(); i++){
cout << ans[i] << " ";
}
}
return 0;
}
"같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다."
sc == answer && ans > tmp
C++에서 vector<int> a; vector<int> b; 로 두개의 벡터가 있을 때 (a > b) or (a < b) 처럼 두 벡터를 사전순으로 비교할 수 있다.
728x90
반응형
'Algorithm > BAEKJOON' 카테고리의 다른 글
[BOJ] 21278번 호석이 두 마리 치킨 (C++) (1) | 2023.11.01 |
---|---|
[BOJ] 7490번 0 만들기 (C++) (0) | 2023.10.30 |
[BOJ] 20055번 컨베이어 벨트 위의 로봇 (C++) [삼성 SW 역량테스트 기출] (0) | 2023.10.01 |
[BOJ] 1781번 컵라면 (C++) (0) | 2023.05.10 |
[BOJ] 15565번 귀여운 라이언 (C++) (0) | 2023.05.05 |