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

문제 출처 : 

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

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

 

 

문제: 

 

 

Point : 부분집합

 

 

코드:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2961_TastyFood {
	
	static int[] sour;
	static int[] bitter;
	static int N;
	
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //재료의 갯수
		StringTokenizer st;
		sour = new int[N];
		bitter= new int[N];
		
		for(int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			sour[i]=Integer.parseInt(st.nextToken());
			bitter[i]=Integer.parseInt(st.nextToken());
		}//입력 완료
		
		int answer = subset(0, 1, 0);
		System.out.println(answer);
	
	}
	
	//cnt번째까지의 재료를 고려해서 그때까지의 쓴맛과 신맛의 차이 리턴
	public static int subset(int cnt, int total_sour, int total_bitter) {
		
		if(cnt==N) {
			
			if(total_sour==1 && total_bitter==0) //재료를 하나도 포함하지 않았을 경우 -> 조건 만족 X
				return Integer.MAX_VALUE;
			
			return Math.abs(total_sour - total_bitter);
		}
		
		
		int a = subset(cnt+1, total_sour*sour[cnt], total_bitter+bitter[cnt]);
		int b = subset(cnt+1, total_sour, total_bitter);
		return Math.min(a, b);
	}

}

 

 

설명:

subset함수에서 total_sour의 초기값이 1인 이유는, 음식의 신맛은 사용한 재료의 신맛의 곱이기 때문입니다.

그리고  부분집합을 구할 경우 공집합도 포함이 되게 되는데, 이때의 total_sour은 1, total_bitter은 0이 됩니다.

하지만 문제에 따르면 재료를 반드시 하나 이상 사용해야 하므로, 공집합인 경우에는 int의 최댓값을 리턴시켜 min값으로 절대 뽑히지 못하게 함으로써 결과에 영향을 미치지 못하게 했습니다.