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

풀이 ①, ② 둘 다 브루트 포스 + 백트래킹 사용,
백트래킹 구현에 약간의 차이

풀이 ①

1. 아이디어

브루트 포스 + 백트래킹: 백트래킹으로 조합(부분 집합)을 구성하고, 구성한 모든 경우를 확인

• n 개의 재료들 중에서 1 ~ n 개 조합 (중복 X, 순서 X) 선택

  • 1개 조합 선택 후, 차이 계산
  • 2개 조합 선택 후, 차이 계산
    ...
  • n 개 조합 선택 후, 차이 계산

• 각 조합들에 대해 맛 최소 차이 갱신해나감

2. 자료구조

• Taste[]: 각 재료들의 신 맛, 쓴 맛
• List<Integer>, ArrayList<Integer>: 선택된 재료들

3. 시간 복잡도

• 조합(Combination): C(n, k) = n! / k! x (n-k)!
• n 최대 10에 대해 C(10, 1) + C(10, 2) + ... + C(10, 10)
  = [ C(10, 1) + C(10, 2) + C(10, 3) + C(10, 4) + C(10, 5) ] x 2
  = 총 1,274 개 경우 << 1억 (1초)

코드

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

class Taste {
	public int sour;		// 신 맛
	public int bitter;		// 쓴 맛

	public Taste(int sour, int bitter) {
		this.sour = sour;
		this.bitter = bitter;
	}
}

public class Main {
	static int n;						// 재료 개수
	static Taste[] tastes;				// 각 재료들의 신 맛, 쓴 맛
	static int minDiff = Integer.MAX_VALUE;			// 출력: 최소 신 맛, 쓴 맛 차이
	static List<Integer> selected;		// 조합: 선택된 재료들

	/* C(n, k) 구성 => k 개 선택 */
	static void combination(int k, int startIdx) {
		if (selected.size() == k) {		// k 개 재료 선택 완료
			int totalSour = 1;
			int totalBitter = 0;

			for (int idx : selected) {
				Taste taste = tastes[idx];
				totalSour *= taste.sour;
				totalBitter += taste.bitter;
			}

			int diff = Math.abs(totalSour - totalBitter);
			minDiff = Math.min(minDiff, diff);
			return;
		}

		for (int i = startIdx; i < n; i++) {
			selected.add(i);
			combination(k, i + 1);

			// 재귀 호출 복귀 => 선택 복구
			selected.remove(Integer.valueOf(i));
		}
	}

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

		n = Integer.parseInt(br.readLine());
		tastes = new Taste[n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int sour = Integer.parseInt(st.nextToken());
			int bitter = Integer.parseInt(st.nextToken());
			tastes[i] = new Taste(sour, bitter);
		}

		// C(n, 1) ~ C(n, n)
		for (int i = 1; i <= n; i++) {
			selected = new ArrayList<>();
			combination(i, 0);
		}

		System.out.println(minDiff);
	}
}

풀이 ② - 재귀호출 2번: 선택 O / 선택 X

다수의 item들을 차례로 확인하면서 해당 item을 선택 O / 선택 X 하는 경우,
풀이 ②의 방식이 조금 더 직관적임

1. 아이디어

브루트 포스 + 백트래킹: 백트래킹으로 조합(부분 집합)을 구성하고, 구성한 모든 경우를 확인

• n 개 재료들을 차례로 확인
  1) idx 번째 재료를 선택하고, 그 다음 재료 확인 (재귀 호출)
  2) idx 번째 재료를 선택하지 않고, 그 다음 재료 확인 (재귀 호출)

• 재귀 호출 종료 조건: n 개 재료들을 모두 확인
  => 맛 차이 계산

• 예외 처리) 재료를 1개도 선택하지 않은 경우는 제외 처리

2. 자료구조

• Taste[]: 각 재료들의 신 맛, 쓴 맛
• List<Integer>, ArrayList<Integer>: 선택된 재료들

3. 시간 복잡도

• 1개 재료에 대해, 2가지 선택

  • 해당 재료 선택 O
  • 해당 재료 선택 X

  => 재귀 호출 2번

• 총 재귀 호출 (전체 경우의 수) = 2^10 = 1,024 << 1억 (1초)

코드

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

class Taste {
	public int sour;		// 신 맛
	public int bitter;		// 쓴 맛

	public Taste(int sour, int bitter) {
		this.sour = sour;
		this.bitter = bitter;
	}
}

public class Main2 {
	static int n;						// 재료 개수
	static Taste[] tastes;				// 각 재료들의 신 맛, 쓴 맛
	static int minDiff = Integer.MAX_VALUE;			// 출력: 최소 신 맛, 쓴 맛 차이
	static List<Integer> selected = new ArrayList<>();		// 선택된 재료들

	static void solution(int depth) {
		if (depth == n) {				// n 개 재료들을 모두 확인한 경우
			if (selected.isEmpty())		// 재료를 1개도 선택하지 않은 경우는 제외
				return;

			int totalSour = 1;
			int totalBitter = 0;

			for (int idx : selected) {
				Taste taste = tastes[idx];
				totalSour *= taste.sour;
				totalBitter += taste.bitter;
			}

			int diff = Math.abs(totalSour - totalBitter);
			minDiff = Math.min(minDiff, diff);
			return;
		}

		selected.add(depth);						// 해당 재료 선택 O
		solution(depth + 1);

		selected.remove(Integer.valueOf(depth));	// 해당 재료 선택 X
		solution(depth + 1);
	}

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

		n = Integer.parseInt(br.readLine());
		tastes = new Taste[n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int sour = Integer.parseInt(st.nextToken());
			int bitter = Integer.parseInt(st.nextToken());
			tastes[i] = new Taste(sour, bitter);
		}

		solution(0);

		System.out.println(minDiff);
	}
}