[Java] 19942번: 다이어트

🌎 Link : https://www.acmicpc.net/problem/19942

19942번: 다이어트

---

💡 접근 방법

1. 문제 이해 & 적합한 알고리즘 찾기

식재료의 각각의 조합에 따라서 원하는 영양소를 넘는 최소비용을 구해야 하기 때문에 백트레킹이 적합해 보인다. 하지만 이전에 풀이했던 문제와 다르게 백트레킹이 탈출할 포인트를 depth가 아닌 다른 부분을 정해야 했다. 항상 depth로만 풀이하다가 조금 혼란스러웠다. 우선 백트레킹의 틀을 어느 정도 작성해 놓고 어떤 것을 구해야 할지 작성해 봤다.

• 영양소를 넘는 식재료의 조합이 1,2,5 = 비용 30 / 1,3,6,7 = 비용 10 이렇게 나올 경우 1,3,6,7을 출력해야 한다. 그렇기 때문에 모든 조합의 수를 탐색하는 식이 필요하다.
• 최소 비용이 갱신될 경우 이전 식재료의 번호를 제거 후 새로운 조합의 식재료 번호를 넣어야 한다

솔직히 다른 부분은 접근하기 쉬웠다. 하지만 모든 조합을 찾아보는 방법에 대해서 구현을 하기 어려워 구글링을 해서 찾아봤다.

참고 블로그 : https://dang2dangdang2.tistory.com/192

[JAVA]백준_19942_다이어트

위 블로그에선 이렇게 문제를 해결하였다 하지만 아무리 디버그를 돌려봐도 내 머리로는 이해가 불가능해 보였다. 왜 저렇게 사용을 하는지 와닿지 않았다. 그래서 다른 방식으로 접근해보려고 했다.

//한개 고르는 것 부터 N개 모두 다 고르는 것 까지 고려
for(int i=1;i<=N;i++){
	isSelected = new int[N];
	dfs(0,i,1);
}
        
static void dfs(int cnt,int choiceNum,int start){...}

 

2. 문제 풀이

이전 백트레킹 문제를 풀었던 양팔저울 : https://www.acmicpc.net/problem/17610 문제를 떠올려서 활용하기로 했다 아래 문제의 경우에 따라 각각 dfs를 돌리면 된다.

17610번: 양팔저울

문제를 떠올려서 활용하기로 했다 위 문제의 경우에 따라 각각 dfs를 돌리면 된다.

private static void dfs(int weight, int depth) {
	if (depth == N) {
		isTrue[weight] = true;
		return;
	}
	
	// 현재 무게(weight)에 다음 추의 무게(arr[depth])를 더한 경우
	dfs(weight + arr[depth], depth + 1);
	// 현재 무게(weight)를 그대로 유지하는 경우
	dfs(weight, depth + 1);
	// 현재 무게(weight)에서 다음 추의 무게(arr[depth])를 뺀 경우
	dfs(Math.abs(weight - arr[depth]), depth + 1);
}

 

이렇게 모든 경우의 수를 재귀를 돌려주면서 주어진 추들로 측정할 수 있는 모든 무게를 찾아낼 수 있었다. 그렇다면 위 방식을 적용할 수 있는 방법은 뭘까?

• 현재 식재료를 포함하는 경우
• 현재 식재료를 포함하지 않는 경우

이렇게 두 가지의 경우를 설정해서 재귀를 돌릴 수가 있다. 최소비용을 구할 수 있게 되었다. 하지만 우리는 어떤 식재료가 포함되는지 식재료의 번호를 담을 List가 필요하고 어떤 식재료를 담을 것인지 규칙이 필요하다.

private static void backtracking() {
    if(탈출조건 : 원하는 영양소를 모두 넘겼을 경우) {
        최소 비용 갱신();
        return;
    }
    
	탈출조건에 도달 하기 위해 경우의 수를 조합해 재귀를 돌린다.
	backtracking(현재 식재료를 포함하는 경우를 넘겨준다);
	backtracking(현재 식재료를 포함하지 않는 경우를 넘겨준다);
}

 

여기서 현재 식재료를 포함하는 경우를 방문체크를 하고 식재료를 포함하지 않는 경우를 넘겨줄 경우 방문체크를 해제해서 보내주면 된다. 또한 답을 출력할 경우 방문체크가 되어있는 식재료만 출력하면 되기 때문에 방문체크를 하는 코드를 추가해 주자.

private static void backtracking(int index, int 영양소 ..., int 누적비용) {
    if(탈출조건 : 원하는 영양소를 모두 넘겼을 경우) {
        최소 비용 갱신(누적비용);
        return;
    }
    
	탈출조건에 도달 하기 위해 경우의 수를 조합해 재귀를 돌린다.
	isVisited[index] = true;
	backtracking(index + 1, 이전 영양소 + 현재 영양소 ..., 이전 누적비용 + 현재 영양소 비용);
	isVisited[index] = false;
	backtracking(index + 1, 이전 영양소, 이전 누적비용);
}

 

이렇게 방문체크를 함으로써 모든 경우의 수를 조합하는 백트레킹 틀을 구현했으니 정해진 값을 넣어줘 구현을 하면 되겠다. 이전 문제와는 다르게 다른 접근을 해야 해서 시간이 오래 걸렸다. 그래도 이 풀이가 이해가 더 잘되는 것 같다. 

---

🗝 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static int N;
    static int cost = Integer.MAX_VALUE;
    static int[] target;
    static boolean[] isVisited;
    static Nutrient[] nutrients;
    static List<Integer> answer = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        nutrients = new Nutrient[N];
        isVisited = new boolean[N];

        target = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for (int i = 0; i < N; i++) {
            nutrients[i] = Nutrient.of(br.readLine());
        }

        backtracking(0, 0, 0, 0, 0, 0);

        if (cost == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(cost);
            for (int a : answer) System.out.print(a + " ");
        }
    }

    public static void backtracking(int index, int p, int f, int c, int v, int amount) {
        if (p >= target[0] && f >= target[1] && c >= target[2] && v >= target[3]) {
            check(amount);
            return;
        }

        if (index >= N || amount >= cost) return;

        isVisited[index] = true;
        backtracking(index + 1, p + nutrients[index].protein, f + nutrients[index].fat,
                c + nutrients[index].crab, v + nutrients[index].vitamin, amount + nutrients[index].price);
        isVisited[index] = false;
        backtracking(index + 1, p, f, c, v, amount);
    }

    private static void check(int amount) {
        if (amount < cost) {
            cost = amount;
            answer.clear();
            for (int i = 0; i < N; i++) {
                if (isVisited[i]) answer.add(i + 1);
            }
        }
    }
}

class Nutrient {
    int protein, fat, crab, vitamin, price;

    public Nutrient(int protein, int fat, int crab, int vitamin, int price) {
        this.protein = protein;
        this.fat = fat;
        this.crab = crab;
        this.vitamin = vitamin;
        this.price = price;
    }

    public static Nutrient of(String food) {
        int[] nutrient = Arrays.stream(food.split(" ")).mapToInt(Integer::parseInt).toArray();

        return new Nutrient(nutrient[0], nutrient[1], nutrient[2], nutrient[3], nutrient[4]);
    }
}