오랜만에 다시 코딩테스트 준비를 위해 알고리즘 공부를 시작하였다.
내가 가장 부족한 탐색 문제 위주로 할 예정이다.

문제

입력

출력

예제

idea

브루트포스 완전 탐색인 것은 알았다.
하지만 푸는 방법을 몰라서 for문으로 막 계산을 하려고 노력하다가 실패했다.
주변 도움을 받아서 순조부에 대하여 공부할 수 있었다.
부분집합을 이용하여 풀었는데 공집합일 경우를 제외해야 하기 때문에 empty_set을 만들어서 공집합일 때는 제외하여 계산하였다.

정리

부분 집합 공식을 이용하여 풀이.
신 맛은 곱하기 이기 때문에 s = 1 쓴 맛은 더하기 이기 때문에 b = 0 으로 둔 후 부분 집합 식을 이용하여 isSelected = true 일 경우에만 계산을 진행하며,
각 집합마다 계산을 끝낸 후 answer와 현재 계산 값 중 더 작은 값이 answer가 되도록 하였다.

Code

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

public class Main {
	
	static int N, totalCnt;
	static int[] numbers, input; //뽑힌 애들
	static boolean[] isSelected;
	static int S[];
	static int B[];
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		S= new int[N];
		B= new int[N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			S[i]=Integer.parseInt(st.nextToken());
			B[i]=Integer.parseInt(st.nextToken());
		}
		
		
		totalCnt = 0;
		
		numbers = new int[N];
		isSelected = new boolean[N];  // 수가 1부터 시작해서 인덱스도 1부터 논리적 매칭 사용
				
		subset(0);
		System.out.println(answer);

	}

	
	private static void subset(int index) { // index : 부분집합에 고려할 대상 원소의 인덱스  cnt : 직전까지 고려한 원소 수
		if(index == N) { // 더이상 고려할 원소가 없다면 부분집합의 구성이 완성
			boolean empty_set = false;
			int s=1, b=0;
			totalCnt++;
			for (int i = 0; i < N; i++) {
				if(isSelected[i]) {
					s*=S[i];
					b+=B[i];
					empty_set=true;
				}
			}
			if(empty_set)
				answer=Math.min(answer, Math.abs(s-b));
			return;
		}
		// 원소 선택
		isSelected[index] = true;
		subset(index+1);

		// 원소 미선택
		isSelected[index] = false;
		subset(index+1);
	}
}

결과