[Java] 도영이가 만든 맛있는 음식 - 백트래킹 (Lv. Sliver2)

도영이가 만든 맛있는 음식 - 백트래킹

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

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

public class Main {
    static int N;
    static int[][] ingre;
    static int answer = Integer.MAX_VALUE;

    public static void favor(int i, int S, int B, int cnt) {
        if (i == N) {
            if (cnt == 0) return;
            int result = Math.abs(S - B);
            answer = Math.min(answer, result);
            return;
        }

        favor(i + 1, S * ingre[i][0], B + ingre[i][1], cnt + 1);
        favor(i + 1, S, B, cnt);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ingre = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            ingre[i][0] = Integer.parseInt(st.nextToken()); 
            ingre[i][1] = Integer.parseInt(st.nextToken()); 
        }

        favor(0, 1, 0, 0);
        System.out.println(answer);
    }
}

 

최적화를 위해서 재귀를 사용했습니다.

if문으로 불필요한 계산을 줄여주었습니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3