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

풀이 방법

부분합 알고리즘을 사용했다. 재료를 고르는 경우 신맛은 곱하고 쓴맛은 더해서 재귀했고
고르지 않는경우는 그대로 재귀했다.

아무것도 뽑지 않는 경우는 제외하고 신맛, 쓴맛의 차이를 리스트에 담은 후
가장 작은 값을 뽑았다.

package com.day9;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class BOJ2961 {
	public static int num;
	public static int[] bitter;
	public static int[] sour;
	public static boolean [] visited;
	public static ArrayList<Integer> list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		num = sc.nextInt();
		bitter = new int [num];
		sour = new int [num];
		visited = new boolean [num];
		
		//리스트에 값 채우기
		list = new ArrayList<>();
		for(int i = 0 ; i < num ; i++) {
			sour[i] = sc.nextInt(); //곱
			bitter[i] = sc.nextInt(); //합	
		}
		
		//num이 1인경우면 바로 차이 구함
		if(num ==1) {
			int difference = Math.abs(sour[0] - bitter[0]);
			list.add(difference);
		}
		else subset(0,1,0);
		
		
		System.out.println(Collections.min(list));
	}

	private static void subset(int depth , int sourMulti , int bittSum) {
		if(depth == num) {
			//방문함수에 전부 false만 있다면 아무것도 뽑지 않은 것
			boolean flag = false;
			for(int i = 0 ; i < visited.length; i++) {
				if(visited[i]) {
					flag = true;
					break;
				}
			}
			//공집합인 경우 리턴
			if(!flag) return;
			
			//두개의 차이를 리스트에 추가
			int difference = Math.abs(sourMulti - bittSum);
			list.add(difference);
			return;
		}
		
		//뽑는경우
		visited[depth] = true;
		subset(depth+1 , sourMulti * sour[depth] , bittSum + bitter[depth]);
		//안뽑는 경우
		visited[depth] = false;
		subset(depth+1, sourMulti , bittSum);
		
	}
}