백준 19942 다이어트 자바(java)

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

19942번: 다이어트

 

풀이 방법

식재료 N개를 하나씩 조합해보면서 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾는데,

이때 백트래킹을 이용하여 시간 단축을 할 수 있도록 하였다.

현재까지 선택된 식재료 조합은 문자열 answer 에 기록한다.

 

1. 먼저, i번째 식재료를 선택하는 경우를 탐색한다.

2. 함수 재귀 호출 시 answer 에 추가해주고 각 영양분에 i번째 식재료의 영양분을 더한다.

3. 만약, 지금까지의 비용 c 가 현재 최소 비용 이상이 되면 더 탐색해도 의미 없으므로 탐색을 멈춘다.

4. 지금까지 더해진 영양분들이 모두 최저 영양소 기준을 만족하는지 확인하고, 만족한다면 정답을 갱신하고 

    탐색을 멈춘다. i가 1부터 증가하면서 탐색하므로 정답은 사전 순으로 빠른 조건을 반드시 만족한다.

5. i 가 N보다 크면 범위를 벗어나므로 탐색을 멈춘다.

6. i 를 선택한 경우의 탐색이 끝나면 돌아와서 i를 선택하지 않은 경우로 재귀 호출하여 똑같이 탐색한다.

7. 선택하지 않는 경우엔 i 인덱스만 증가시켜 재귀 호출한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int minCost = 987654321;
    static String answer = "";
    static int[] standard;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        standard = new int[4];

        // 최소 영양성분 입력
        String[] ingredient = br.readLine().split(" ");
        for(int i=0; i<4; i++) {
            standard[i] = Integer.parseInt(ingredient[i]);
        }

        // N개의 식재료의 영양성분 입력
        arr = new int[N+1][5];
        for(int i=1; i<=N; i++){
            ingredient = br.readLine().split(" ");
            for(int j=0; j<5; j++) {
                arr[i][j] = Integer.parseInt(ingredient[j]);
            }
        }

        backtracking("", 1, 0, 0, 0, 0, 0);

        if(answer.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(minCost);
            System.out.println(answer.trim());
        }
    }

    public static void backtracking(String comb, int i, int p, int f, int s, int v, int c) {

        // 더 이상 탐색할 필요 없으므로 리턴
        if(c >= minCost) {
            return;
        }
        // 최소 영양성분을 모두 맞췄다면 최소 비용 갱신
        if(p >= standard[0] && f >= standard[1] && s >= standard[2] && v >= standard[3]) {
            minCost = c;
            answer = comb;
            return;
        }

        if(i > N){
            return;
        }

        backtracking(comb + " " + i, i+1, p+arr[i][0], f+arr[i][1], s+arr[i][2], v+arr[i][3], c+arr[i][4]);
        backtracking(comb, i+1, p, f, s, v, c);
    }
}