[BOJ] 백준 2961 - 도영이가 만든 맛있는 음식 풀이

1. 문제

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

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

 

2. 풀이

백준 실버 2의 브루트포스 및 백트래킹 문제이다.
백트래킹을 어떻게 설정해야하는지 몰랐던 문제였고, 백트래킹에 대한 이해가 너무 부족하다고 느낀 문제였다.

우선 이 문제는 모든 경우의 수를 전부 탐색해야 하기 때문에 단순한 반복문으로는 해결이 안되는 문제이다.
입력을 받고 다음의 변수를 설정한다.

1. input_cnt = 요리에 들어간 재료의 개수
2. s_mul = 신맛의 곱
3. b_hap = 쓴맛의 합
4. idx = 재료의 인덱스

그 후 재귀 함수를 만들고 두 가지의 경우를 통해 함수를 재귀호출한다.
1. idx + 1번째의 재료를 넣지 않는 경우
2. idx + 1번째의 재료를 넣은 경우

이러면 모든 경우의 수를 탐색할 수 있으며 재귀 호출 할 때마다 idx를 하나씩 증가시켜줬기 때문에 중단점을 만들어줘야한다.
그 중단점은 45번째 줄이며, idx가 재료의 개수만큼 도달했을 때 재료를 하나 이상 넣었다면 (46줄) 그 때 min 값을 최신화한다.

마지막으로 min 값을 출력하면 정답!!

 

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class FoodIngredient {
        int S = 0;
        int B = 0;

        public FoodIngredient(int s, int b) {
            S = s;
            B = b;
        }
    }

    static int min = Integer.MAX_VALUE;
    static int foodIngredientCnt;
    static List<FoodIngredient> foodIngredientList = new ArrayList<>();

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

        foodIngredientCnt = Integer.parseInt(br.readLine());
        for (int i = 0; i < foodIngredientCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            foodIngredientList.add(new FoodIngredient(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int input_cnt = 0;
        int s_mul = 1;
        int b_hap = 0;
        int idx = 0;

        setMinResult(input_cnt, idx, s_mul, b_hap);

        bw.write(Integer.toString(min) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void setMinResult(int input_cnt, int idx, int s_mul, int b_hap) {
        if (idx == foodIngredientCnt) {
            if(input_cnt != 0) {
                min = Math.min(min, Math.abs(s_mul - b_hap));
            }
            return;
        }
        setMinResult(input_cnt, idx + 1, s_mul, b_hap); // 재료 넣지 않은 것
        setMinResult(input_cnt + 1, idx + 1, s_mul * foodIngredientList.get(idx).S, b_hap + foodIngredientList.get(idx).B); // 재료를 넣은 것
    }
}