[백준/boj] 2961: 도영이가 만든 맛있는 음식 (Java) / 브루트포스 알고리즘 / 부분 집합

문제

풀이

import java.util.*;
import java.io.*;

public class Main_BOJ_2961_도영이가만든맛있는음식 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int[][] foodInfo;
	static boolean[] isSelected;
	static long divOfScore;

	public static void main(String[] args) throws Exception {
		int N = stoi(br.readLine());
		foodInfo = new int[N][2];
		isSelected = new boolean[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			foodInfo[i][0] = stoi(st.nextToken());
			foodInfo[i][1] = stoi(st.nextToken());
		}
		divOfScore = Long.MAX_VALUE;
		generateSubset(0);
		bw.append(divOfScore + "");
		bw.flush();
		bw.close();
	}

	private static void generateSubset(int cnt) {
		boolean isZeroSelected = false;
		if (cnt == foodInfo.length) { 
			long sTotal = 1;
			long bTotal = 0;

			for (int i = 0; i < foodInfo.length; i++) {
				if (isSelected[i]) { // 선택 되어있으면
					sTotal *= foodInfo[i][0];
					bTotal += foodInfo[i][1];
					isZeroSelected = true;
				}
			}
			if(!isZeroSelected) return;
			divOfScore = Math.min(divOfScore, Math.abs(sTotal - bTotal));
			return;
		}
		isSelected[cnt] = true; // 선택
		generateSubset(cnt + 1);
		isSelected[cnt] = false; // 비선택
		generateSubset(cnt + 1);
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

완전 탐색과 부분 집합으로 푸는 문제이다. 

foodInfo[i][0] 은 i번째 음식의 신 맛을 의미하고, foodInfo[i][1]은 i번째 음식의 쓴 맛을 의미한다. 

boolean 배열의 isSelected 를 사용해 해당 음식이 선택된 경우와 선택 되지 않은 경우를 설정한 후, 함수를 호출(재귀)한다.

이때 주의할 점은 ! cnt++ 이 아니라 cnt + 1을 사용해야한다는 점이다. cnt 자체를 변경하면 안된다. 

이제 N개 음식의 선택 상태가 결정되면 선택된 경우의 음식(isSelected[i] == true)만 신맛은 곱하고 (*) 쓴맛은 더한다 (+). 

그 후 선택된 음식의 신맛을 모두 곱한 것에서 쓴맛을 모두 더한 값의 절댓값(Math.abs(sTotal - bTotal))을 계속 최솟값으로 갱신한다.

그 최솟값(divOfScore)가 답이 된다. 

long 자료형을 쓴 이유
신 맛과 쓴 맛이 최대 1,000,000,000 - 1 이기 때문에 
최대로 올수 있는 sTotal은 (1,000,000,000 - 1) ^ 10 이 된다. 이는 int 의 범위를 넘어서기 때문에 long 을 사용했다. 
범위 제한이 없는 자료형을 쓰고 싶다면 BigInteger를 쓰면 된다. 

추가 ) long으로 안하고 int로 해도 맞았습니다가 나온다고 한다.