[BOJ]2961号:道英が作ったグルメ(Java)

質問する

2961号:道英が作ったグルメ

に答える

材料を組み合わせると、苦味の酸味の差が最小になります.
したがって、「組合せ」アルゴリズムを使用して問題を解決します.
組み合わせた後、基本条件を満たせば、この組み合わせの酸味と苦味が得られ、組み合わせの中で最高価格を探すことができる.

コード#コード#

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

public class Main{
	static int n;
	static int[][] tasty;
	static boolean[] isSelected;
	static int min=Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		tasty = new int[n][2];
		isSelected = new boolean[n];
		for(int i =0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			tasty[i][0] = Integer.parseInt(st.nextToken());
			tasty[i][1] = Integer.parseInt(st.nextToken());
		}
		cook(0);
		System.out.println(min);
		br.close();
	}

	public static void cook(int cnt) {
		int sour = 1;
		int bitter = 0;
		if(cnt == n) {
			for(int i =0 ; i < n ; i++) {
				if(isSelected[i]) {
					sour *= tasty[i][0];
					bitter += tasty[i][1];
				}
			}
			if(sour!= 1 && bitter!=0) min = Math.min(min, Math.abs(sour-bitter));
			return;
		}
		isSelected[cnt] = true;
		cook(cnt+1);
		isSelected[cnt] = false;
		cook(cnt+1);
	}
}