[BOJ/Java] 2961. 도영이가 만든 맛있는 음식

[BOJ/Java] 2961. 도영이가 만든 맛있는 음식

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

---

풀이

package edu.ssafy.im.BOJ.S2.No2961;

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

public class Main {
    static int[] s, b; // 각 재료의 신맛과 쓴맛을 저장하는 배열
    static int ans; // 결과값을 저장할 변수

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine()); // 재료의 개수 입력 받기
        s = new int[n]; // 신맛을 저장할 배열 초기화
        b = new int[n]; // 쓴맛을 저장할 배열 초기화
        for (int i = 0; i < n; i++) {
            // 각 재료의 신맛과 쓴맛 입력 받기
            String input = br.readLine();
            StringTokenizer st = new StringTokenizer(input);
            s[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }
        ans = Integer.MAX_VALUE; // 결과값 초기화
        powerSet(0, new boolean[n]); // 부분집합 구하기
        sb.append(ans); // 결과값 출력을 위한 문자열에 추가
        System.out.println(sb); // 결과 출력
    }

    private static void powerSet(int i, boolean[] v) {
        // basis part
        if(i == v.length) { // 모든 재료를 선택했을 때
            int ss = 1, bs = 0, c = 0; // 각각 신맛과 쓴맛, 미사용된 재료의 개수를 저장할 변수
            for (int j = 0; j < v.length; j++) {
                if(v[j]) { // 현재 재료를 사용했을 때
                    ss *= s[j]; // 신맛에 현재 재료의 신맛을 곱함
                    bs += b[j]; // 쓴맛에 현재 재료의 쓴맛을 더함
                } else {
                    c++; // 미사용된 재료의 개수 증가
                }
            }
            if(c != v.length) { // 모든 재료를 사용한 경우가 아닐 때
                ans = Math.min(ans, Math.abs(ss - bs)); // 현재까지의 결과값 갱신
            }
            return;
        }

        // inductive part
        // 현재 재료를 사용하는 경우와 사용하지 않는 경우를 모두 탐색
        v[i] = true; // 현재 재료를 사용하는 경우
        powerSet(i + 1, v); // 다음 재료로 넘어감
        v[i] = false; // 현재 재료를 사용하지 않는 경우
        powerSet(i + 1, v); // 다음 재료로 넘어감
    }
}