[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);
	}
}