📚 2961 - 도영이가 만든 맛있는 음식

도영이가 만든 맛있는 음식

이해

도영이가 만든 맛있는 음식 문제, 재료 N개가 있다.
신맛 S와 쓴맛 B가 있을 때

• 신맛은 신맛들의 곱으로 계산
• 쓴맛은 쓴맛들의 합으로 계산

신맛과 쓴맛 차이가 가장 작은 요리를 만드는 프로그램

→ dfs를 통해 구현하면 된다. (깊이 우선 탐색)

소스

package Online.ws0811_1;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class BJ2961 {  
    static int N;  
    static int[][] arr;  
    static int result;  
  
    public static void dfs(int material, int idx, int sour, int bitter) {  
        if (idx == N) {  
            if (material != 0) {  
                // 하나라도 체크 했다면 확인한다.  
                result = Math.min(result, Math.abs(sour - bitter));  
            }  
  
  
            return;  
        }  
  
        dfs(material, idx + 1, sour, bitter);  
        dfs(material + 1, idx + 1, sour * arr[idx][0], bitter + arr[idx][1]);  
    }  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
        arr = new int[N][2];  
        for (int i = 0; i < N; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            arr[i][0] = Integer.parseInt(st.nextToken());  
            arr[i][1] = Integer.parseInt(st.nextToken());  
        }  
        result = Integer.MAX_VALUE;  
        dfs(0, 0, 1, 0);  
        System.out.println(result);  
        br.close();  
    }  
}