백준 [2961] 도영이가 만든 맛있는 음식 (자바)

문제

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

풀이

백트래킹과 브루트 포스 알고리즘을 사용한다.

재료를 선택하여 조합할 수 있는 모든 경우를 탐색하면서 쓴맛과 신맛의 차이가 가장 작은 경우 그 재료 조합을 갱신해준다.

재료를 적어도 하나 이상 선택한 경우이고 차이가 갱신된 최소값보다 더 작은 경우 최소값을 갱신한다.

정답코드

package com.baekjoon.p2961;

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

public class Main {
    static int N, min;
    static int[] S;
    static int[] B;
    static boolean[] v;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        S = new int[N];
        B = new int[N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            S[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        min = Integer.MAX_VALUE;
        dfs(1, 0, 0, 0);
        System.out.println(min);
    }

    static void dfs(int s, int b, int depth, int selected) {
        if (depth == N) {
            /**
             * 하나 이상이 선택되어 있어야 하므로 selected가 1이상인지 확인
             * 쓴맛과 신맛의 차이 값을 갱신
             */
            if (selected != 0 && Math.abs(s - b) < min) {
                min = Math.abs(s - b);
            }
            return;
        }

        dfs(s * S[depth], b + B[depth], depth + 1, selected + 1); // 선택한 경우
        dfs(s, b, depth + 1, selected); // 선택하지 않은 경우
    }
}