개발일지/Algorithm
백준 - 19942 다이어트 [백트래킹]
E-room
2023. 10. 6. 22:17
728x90
19942번: 다이어트
식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각
www.acmicpc.net
1. 문제 요약
N개의 식재료가 주어지고, 해당 식재료를 이용하여 영양성분을 만족하는 최저 비용 조합을 구하라
2. 접근 방법
- 재귀함수를 이용하여 모든 조합을 구한다.
- 영양성분을 만족하는 조합들 중 최저 비용을 계산한다.
3. 파이썬
def solution(index:int, used:list):
global C, USED
if index == N:
p, f, s, v, c = 0, 0, 0, 0, 0
for i in used:
p += PFSVC[i-1][0]
f += PFSVC[i-1][1]
s += PFSVC[i-1][2]
v += PFSVC[i-1][3]
c += PFSVC[i-1][4]
if p >= P and f >= F and s >= S and v >= V:
if c < C or (c == C and used < USED):
C = c
USED = used
return
# 사용하거나
solution(index+1, used + [index+1])
# 사용하지 않거나
solution(index+1, used)
4. 자바
static private void recursive(int index, int[] used) {
if (index == PFSVC.length) {
int p = 0;
int f = 0;
int s = 0;
int v = 0;
int c = 0;
for (int i : used) {
p += PFSVC[i - 1][0];
f += PFSVC[i - 1][1];
s += PFSVC[i - 1][2];
v += PFSVC[i - 1][3];
c += PFSVC[i - 1][4];
}
if (p >= P && f >= F && s >= S && v >= V) {
if (c < C || (c == C && Arrays.compare(used, USED) == -1)) {
C = c;
USED = used;
}
}
return;
}
int[] copyOf = Arrays.copyOf(used, used.length + 1);
copyOf[used.length] = index + 1;
recursive(index + 1, copyOf);
recursive(index + 1, used);
}
5. 전체 코드
728x90