[백준, Java] 19942번, 다이어트(백트래킹)

문제 링크

19942번: 다이어트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 각 재료에는 영양분과 가격이 주어집니다.

2. 각 재료 중 몇 개를 선택해서 음식을 만들 수 있으며, 영양분은 해당 재료들의 합입니다.

3. 음식에 대한 최소 영양분이 존재합니다.

4. 최소 영양분을 만족하는 음식을 만드는 최소 비용과 사용된 재료의 번호를 결과로 출력합니다.

5. 최소 영양분을 만족하는 음식이 없다면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. DP와 백트래킹을 이용한 재료 조합을 탐색합니다.

 

3. 탐색한 뒤 얻은 음식의 재료들을 결과로 출력합니다.

 

 

비트 마스킹

 

10001 비트를 해석하면

→ 1번, 5번 재료를 사용했다는 의미입니다.

 

즉, 각 비트의 위치에 있는 재료를 사용했다고 보면 됩니다.

 

비트를 사용한다면 해당 재료를 사용했는지 확인도 가능합니다.

 

예를 들어, 3번 재료에 대한 비트는 100으로 표현할 수 있습니다.

 

10001비트에 3번 재료가 사용되었는지 확인하려면

 

(10001 & 100) == 0을 만족하면 해당 재료를 사용하지 않은 것입니다.

즉,  AND(&)연산으로 사용하지 않은 지 확인하고, 사용했다고 표현할 때에는 OR(|)으로 설정합니다.

 

백 트래킹

 

DP(동적 프로그래밍)을 이용해서 중복된 연산을 최소화하기 위한 배열을 설정합니다.

 

 DP[]의 값이 0이 아니면 이미 계산된 값으로서 해당 값을 사용하도록 해서 반복된 연산을 방지합니다.

 

DP[]의 값을 넣을 때에는 최소 영양분이 모두 만족하는지 확인한 뒤 설정해야 합니다.

 

만약, 모든 재료를 사용하였지만 최소 영양분을 만족하지 못하면 가격으로 나올 수 없는 값 7501을 설정하였습니다.

 

이후 완전탐색을 진행하면서, DP[]에 대한 연산값이 존재하면, 이미 계산한 것이기 때문에 백트래킹을 진행합니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 6

 

최소 영양분

 

mp	mf	ms	mv
100	70	90	10

 

재료 영양분

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

2. DP와 백트래킹을 이용한 재료 조합을 탐색합니다.

 

첫 번째 재료로 1번 재료 사용

 

비트 : 000001

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

현재 영양분

 

단백질	지방	탄수화물	비타민
30	55	10	8

 

 

두 번째 재료로 2번 재료 사용

 

비트 : 000011

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

현재 영양분

 

단백질	지방	탄수화물	비타민
90	65	20	10

 

.....

 

위 과정을 반복합니다.

 

정답이 되는 음식의 과정을 보여드리겠습니다. 

 

 

첫 번째 재료로 2번 재료 사용

 

비트 : 000010

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

현재 영양분

 

단백질	지방	탄수화물	비타민
60	10	10	2

 

두 번째 재료로 4번 재료 사용

 

비트 : 001010

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

현재 영양분

 

단백질	지방	탄수화물	비타민
100	40	40	10

 

세 번째 재료로 6번 재료 사용

 

비트 : 101010

 

	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	4

 

현재 영양분

 

단백질	지방	탄수화물	비타민
120	110	90	14

 

최소 영양분을 만족하며, 모든 조합에서 가격(134)이 저렴함합니다.

 

 

 

3. 탐색한 뒤 얻은 음식의 재료들을 결과로 출력합니다.

음식의 가격 : 134

 

사용한 음식 : 비트(101010) = 2, 4, 6번째 재료 사용

 

134

2 4 6을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N, 최소 영양분 및 재료 정보를 띄어쓰기 기준 구분합니다.
• 비트마스킹 및 백트래킹을 이용하여 재료의 조합들을 만들어보는 search함수를 실행합니다.
• 탐색을 하였는데도 최소값이 INF일 때에는 -1을 결과로 BufferedWriter 저장합니다.
• 최소값이 INF가 아니면, 최소 비용과 비트마스킹을 이용한 재료의 번호를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 DP와 백트래킹을 통해서 중복된 연산을 방지합니다.
• search함수는 비트마스크를 이용해서 사용한 재료를 검사합니다.
• search함수는 재귀를 통해서 재료의 조합을 진행합니다.

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    //비트 마스크, 가격 정보 관련 클래스
    static class Info{
        int bitMask;	//현재 비트마스크
        int price;		//현재 가격
        public Info (int bitMask, int price){
            this.bitMask = bitMask;
            this.price = price;
        }
    }
    //fullMask : 재료 모두 사용되었을 때 비트마스크
    static int fullMask, N;
    static int[] min = new int[4];	//최소 영양분 저장 배열
    static int[][] ingredients;	//재료 정보 저장 배열
    static Info[] DP;	//재연산을 방지할 DP 배열
    static final int INF = 7501;	//가격으로 나올 수 없는 최대 값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        DP = new Info[1<<N];
        fullMask = (1<<N)-1;	//모든 재료 사용했을 때 비트마스크 설정
        StringTokenizer st;
        st = new StringTokenizer(br.readLine()," ");
        //최소 영양분 저장
        for(int i=0;i<4;i++){
            min[i] = Integer.parseInt(st.nextToken());
        }
        ingredients = new int[N][5];
        //재료 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<5;j++){
                ingredients[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //백트래킹 탐색을 통한 최소 가격의 음식 재료 구하기
        Info result = search(0, 0, 0, 0, 0, 0);
        StringBuilder sb = new StringBuilder();
        //최소 영양분 만족하는 음식이 없을 때
        if(result.price == INF){
            sb.append(-1);
        }else{
            //최소 영양분 관련 정보 StringBuilder 저장
            sb.append(result.price).append("\n");
            for(int i=0;i<N;i++){
                if((result.bitMask & (1 << i)) > 0){
                    sb.append(i+1).append(" ");
                }
            }
        }
        bw.write(sb.toString());		//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹을 통한 재료 조합 찾는 재귀 함수
    static Info search(int bitmask, int price, int mp, int mf, int ms, int mv){
        //이미 방문한 재료 조합일 경우
        if(DP[bitmask] != null){
            return DP[bitmask];
        }
        //최소 영양분을 만족하는 재료 조합일 때
        if(mp >= min[0] && mf >= min[1] && ms >= min[2] && mv >= min[3]){
            return DP[bitmask] = new Info(bitmask, price);
        }
        //모든 재료를 사용했을 때
        if(bitmask == fullMask){
            return DP[bitmask] = new Info(bitmask, INF);
        }
        //기본 값 설정
        DP[bitmask] = new Info(bitmask, INF);
        //다른 재료 합치기
        for(int i=0;i<N;i++){
            //해당 재료 사용되지 않았을 때
            if((bitmask & (1 << i)) == 0){
                //합쳤을 때 비트마스크
                int nextMask = bitmask | (1 << i);
                Info temp = search(nextMask, price + ingredients[i][4], mp + ingredients[i][0],
                        mf + ingredients[i][1], ms + ingredients[i][2], mv + ingredients[i][3]);
                //최소값 구하기
                if(DP[bitmask].price > temp.price){
                    DP[bitmask] = temp;
                }
            }
        }
        return DP[bitmask];
    }
}