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

📌문제 링크

---

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

📌문제 설명

---

최악의 경우가 2^10의 경우밖에 없기에 넉넉한 문제입니다. 재료 배열을 돌며 끝까지 탐색했을때에 최솟값을 찾아 출력하면 됩니다.

📌코드

---

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

class Pair {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static ArrayList<Pair> list = new ArrayList<>();
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        input();
        backTracking(0, 1, 0, 0);
        System.out.println(answer);
    }

    public static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Pair(x, y));
        }
        br.close();
    }

    public static void backTracking(int idx, int a, int b, int count) {
        if (idx == N) {
            if (count > 0) { // 최소 하나의 재료는 사용해야 함
                answer = Math.min(answer, Math.abs(a - b));
            }
            return;
        }

        // 현재 재료를 사용하는 경우
        backTracking(idx + 1, a * list.get(idx).x, b + list.get(idx).y, count + 1);

        // 현재 재료를 사용하지 않는 경우
        backTracking(idx + 1, a, b, count);
    }
}