[BOJ] 2961: 도영이가 만든 맛있는 음식 (JAVA)

문제

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

 

여담

하나의 재료에 포함된 신맛과 쓴맛인 줄 모르고 각각 나눠서 생각해서 헤맸다. 다행히 반례 예제가 주어져서 틀렸습니다를 마주하지는 않았다. 나름 다 정리하고 풀었는데 또 제대로 읽지 않았나 보다.. 차근차근 고쳐나가야지😢

 

풀이

주어지는 재료의 수가 최대 10개이므로, 완전 탐색을 통해 풀이할 수 있다.

 

각 재료의 신맛과 쓴맛을 배열에 저장한 뒤, 완탐을 수행하면 된다. 풀이 로직은 다음과 같다.

1. 재료를 적어도 하나 사용했다면 신맛과 쓴맛의 차이가 더 작은 값으로 갱신하기
   • minDiff = Math.min(minDiff, Math.abs(sTaste - bTaste))
2. 모든 재료를 다 탐색했으면 탐색을 종료하기
3. 해당 재료를 선택한 경우와 선택하지 않은 경우로 나누어서 재귀 호출하기
   • 해당 재료를 선택한 경우
     • dfs(depth + 1, cnt + 1, sTaste * sTastes[depth], bTaste + bTastes[depth])
   • 해당 재료를 선택하지 않은 경우
     • dfs(depth + 1, cnt, sTaste, bTaste)

 

코드

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

public class Main {
    static int n, minDiff = Integer.MAX_VALUE;
    static int[] sTastes, bTastes;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sTastes = new int[n]; // 신맛
        bTastes = new int[n]; // 쓴맛
        for (int i = 0; i < n; i++) { // 각 재료의 신맛과 쓴맛 정보 저장
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            sTastes[i] = Integer.parseInt(st.nextToken());
            bTastes[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0, 1, 0);
        System.out.println(minDiff);
    }

    static void dfs(int depth, int cnt, int sTaste, int bTaste) {
        if (cnt > 0) { // 재료를 적어도 하나 사용한 경우
            // 신맛과 쓴맛의 차이가 더 작은 값으로 갱신
            minDiff = Math.min(minDiff, Math.abs(sTaste - bTaste));
        }

        if (depth == n) { // 모든 재료를 다 탐색했으면 탐색 종료
            return;
        }
        // 해당 재료 사용 O
        dfs(depth + 1, cnt + 1, sTaste * sTastes[depth], bTaste + bTastes[depth]);
        // 해당 재료 사용 X
        dfs(depth + 1, cnt, sTaste, bTaste);
    }
}

---