백준 - 19942 다이어트 [백트래킹]

 

19942번: 다이어트

 

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. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/19942.%E2%80%85%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8