[백준/JAVA] 2961번: 도영이가 만든 맛있는 음식

📖 문제

2961번: 도영이가 만든 맛있는 음식

 

 

💡  풀이 방식

• 브루트포스 + 백트래킹 

1~N개의 재료(브루트포스) 조합을 만들면서(백트래킹), 원하는 갯수만큼 뽑힌 재료들의 (신맛 - 쓴맛)의 차이를 가장 작은 요리의 차이와 비교해 갱신한다.

 

 

1~N까지 N번 백트래킹을 실행한다.

DFS의 인자는 아래와 같다.

재료를 뽑을 때마다 신맛과 쓴맛 인자를 갱신해 사용 가능하다.

DFS(사용할 재료 idx, 지금껏 사용한 재료 수 cnt, 사용할 재료 수 target, 신맛 sour, 쓴맛 bitter)

 

재료를 원하는 갯수 target만큼 뽑았다면 여태까지 구한 신맛과 쓴맛의 맛의 차이를 구하고, 이를 최솟값과 비교해 더 작은 값으로 갱신한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX = 1_000_000_000;
    static int N, S, B;
    
    static int[][] arr;
    
    static List<Integer> list = new ArrayList<>();  // 뽑은 재료 리스트
    static int minDiff = MAX - 1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());    // 재료 개수
        arr = new int[N][2];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int S = Integer.parseInt(st.nextToken());   // 신맛 : 곱
            int B = Integer.parseInt(st.nextToken());   // 쓴맛 : 합
            
            arr[i][0] = S;
            arr[i][1] = B;
        }
        
        // [백트래킹] 재료 고르기 1~N개
        for(int i = 1 ; i <= N ; i++) {
            dfs(0, 0, i, 1, 0); // (재료 idx, 사용한 재료 수, 목표 재료 수, 신맛, 쓴맛)
        }
        
        System.out.println(minDiff);
    }
    
    // [백트래킹] (재료 idx, 지금까지 뽑은 재료 수, 뽑아야 하는 재료 수, 신맛, 쓴맛)
    private static void dfs(int idx, int cnt, int target, int sour, int bitter) {
        // 원하는 갯수만큼 뽑았을 때 신맛과 쓴맛의 차이 구해 최솟값과 갱신
        if(cnt == target) { 
            minDiff = Math.min(minDiff, Math.abs(sour - bitter));
            return;
        }
        
        for(int i = idx ; i < N ; i++) {    // 중복 제거하고 뽑기
            list.add(i);
            dfs(i + 1, cnt + 1, target, sour * arr[i][0], bitter + arr[i][1]);  // 신맛과 쓴맛은 누적해 저장
            list.remove(list.size() - 1);
        }
    }
}
 

 

 

➕ 다른 풀이 방식

1) 나처럼 1~N개 재료 안 뽑고 DFS로  처리하시는 방식으로 하셨다.

(이게 문제의 의도에 맞는 방법인 듯 하여 다음엔 나도 이렇게 풀도록 해야겠다...)

import java.io.*;
import java.util.*;

public class Main {
    static int min = Integer.MAX_VALUE;
    static int N;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0, 1, 0);	// (요리에 들어간 재료 갯수, 재료 인덱스, 신맛, 쓴맛)
        System.out.println(min);
    }

    private static void dfs(int inputCnt, int idx, int sour, int bitter) {
        if(idx == N) {
            if(inputCnt != 0) {
                min = Math.min(min, Math.abs(sour - bitter));
            }
            return;
        }
        
        dfs(inputCnt + 1, idx + 1, sour * arr[idx][0], bitter + arr[idx][1]);	// 재료 선택 YES
        dfs(inputCnt,     idx + 1, sour, bitter);	                      // 재료 선택 NO
    }
}

[JAVA] 백준 2961 도영이가 만든 맛있는 음식

[BOJ] 백준 2961 - 도영이가 만든 맛있는 음식 풀이

 

 

 

2) 브루트포스와 비트마스킹을 사용한 방식

(비트마스킹으로 해당 재료의 사용여부를 정할 수 있다.)

int len = 1<<N;	// 모든 경우의 수

for(int i = 1 ; i < len ; i++){
    int sour = 1;
    int bitter = 0;
    
    for(int j = 0; j < n ; j++){	// 각 재료에 대해
        if((i & 1<<j) > 0){ 	// 비트가 1인 경우, 해당 재료가 있다고 판단
            sour *= arr[j][0];
            bitter += arr[j][1];
        }
    }
    
    min = Math.min(min, Math.abs(sour-bitter));
}

백준 2961 도영이가 만든 맛있는 음식 java (brute force, bit masking)

[백준 2961] 도영이가 만든 맛있는 음식(Java) 정리

---

💦 어려웠던 점

- 35분 소요..! 더 빨리 풀 수 있을 것 같다. 비트마스킹으로 푸는 방법도 익혀두자...

 

 

 

1회독	2회독	3회독	4회독	5회독
V