[자바 백준 2961] 도영이가 만든 맛있는 음식

부분집합을 이용하여 풀의하는 알고리즘 문제이다.

신맛, 쓴맛의 배열을 각각 받고 배열들의 부분집합의 합-곱 의 절대값 차가 가장 작은 값을 변수 min 값에 저장하여 문제를 풀었다.

 

먼저 코드는 다음과 같다.

package baekjoon;

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

/**
 * 부분집합을 이용한 알고리즘 풀의
 * @author Yookyoung
 *
 */
public class BJ2961 {

	private static int n;
	private static int[] sour;
	private static int[] bitter;
	private static boolean[] isSelected;
	
	private static int min;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(st.nextToken());
		sour = new int[n];
		bitter = new int[n];
		isSelected = new boolean[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());
		}

//		System.out.println(Arrays.toString(bitter));
		min = Integer.MAX_VALUE;
		Subset(0);
		// 부분합 구해서 신맛은 부분합 끼리 곱하기, 쓴맛은 부분합끼리 더하기, 조합
		System.out.println(min);

	}

	public static void Subset(int cnt) {
		// 제어문
		if (cnt == n) {
			int sum_sour = 1;
			int sum_bitter = 0;
			int index = 0;
			for (int i = 0; i < n; i++) {
				if (isSelected[i]) {
					index++;
					sum_sour *= sour[i];
					sum_bitter += bitter[i];
				}
			}
			if(index == 0)
				return; //공집합
			min=Math.min(min, Math.abs(sum_sour-sum_bitter));
			return;
		}

		isSelected[cnt] = true; // 뽑은경우
		Subset(cnt + 1);
		isSelected[cnt] = false; // 안뽑은 경우
		Subset(cnt + 1);
	}

}

 

재귀 + 부분집합을 구하는 법을 알면 풀기 쉬운 문제이다.

문제 복습및 정리를 하고자 한다.

 

재귀 파트는 크게 종료파트와 진행파트로 이루어져 있다. 

public static void Subset(int cnt) {
		// 제어문
		if (cnt == n) {
			for (int i = 0; i < n; i++) {
				if (isSelected[i]) {
					...
				}
			}
			if(index == 0)
				return; //공집합
			min=Math.min(min, Math.abs(sum_sour-sum_bitter));
			return;
		}

		isSelected[cnt] = true; // 뽑은경우
		Subset(cnt + 1);
		isSelected[cnt] = false; // 안뽑은 경우
		Subset(cnt + 1);
	}

 

Boolean isSelected 배열을 생성하고 뽑았는지 안뽑았는지의 여부만 판단해준다.

뽑은 경우에도 다음 칸으로 이동하여 진행, 안뽑은 경우에도 다음 칸으로 이동하여 진행