[백준(Baekjoon)] 2961. 도영이가 만든 맛있는 음식

 

 

[백준(Baekjoon)] 2961. 도영이가 만든 맛있는 음식

 

 

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

 

 

[입력]

 

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

 

 

[출력]

 

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

 

 

[풀이]

 

재료를 조합하는 경우이고 선택 갯수는 상관없어서 부분집합을 이용해 풀어주었다.

단, 재료를 0개 선택하는 경우는 없으니 부분집합이 공집합일 경우는 sel 변수를 이용해 제외했다.

 

 

 

public class algo2961 {

	static int[][] input; //재료의 신맛과 단맛
	static int N; //재료의 수
	static int S = 1; //신맛 (곱한거)
	static int B = 0; //쓴맛 (더한거)
	static int R = Integer.MAX_VALUE;
	static int sel = 0; //0을 선택한 경우 빼기 위해 표시
	static boolean[] isSelected;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N][2];
		isSelected = new boolean[N];
		
		for(int i = 0; i < N; i++)
		{
			input[i][0] = sc.nextInt();
			input[i][1] = sc.nextInt();
		}
		
		subSet(0);
		System.out.println(R);
	}
	
	public static void subSet(int cnt) {
		if(cnt == N) {
			for (int i = 0; i < N; i++) {
				if(isSelected[i]) {
					sel = 1; //선택한게 하나라도 있으면 1표시
					S *= input[i][0];
					B += input[i][1];
				}
			}
			if(sel == 0) return; //선택한게 없는 경우는 리턴
			R = Math.min(R, Math.abs(S-B)); //신맛과 단맛의 차 절댓값으로 비교
            
            	//변수 초기화
			S = 1;
			B = 0;
			sel = 0;
			return;
			
		}
		
		isSelected[cnt] = true;
		subSet(cnt+1);
		isSelected[cnt] = false;
		subSet(cnt+1);
		
	}

}

 

 

메모리	시간	언어	코드 길이
17556	224	Java 11	910