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

문제 설명

• 조건을 만족하는 적절한 조합을 찾는 문제입니다.

접근법

• 재료의 개수가 적기 때문에 부분집합으로 풀 수 있습니다.
  • 부분집합은 해당 값 선택 + 재귀함수 그리고 해당 값 선택X + 재귀함수를 통해 구현할 수 있습니다.
  • 선택X를 food(1,0)으로 설정했습니다.
  • 선택 or 선택X가 반드시 들어오기 때문에 depth ==N일때 종료하면 됩니다.
• 신맛과 쓴맛의 값을 담기 위해 food class를 생성했습니다.

정답

import java.util.*;

public class Main {
	static int N;
	static food[] s; // 입력으로 들어오는 재료를 담는 변수입니다.
	static food[] answer; // 부분집합으로 만든 결과를 담는 변수입니다.
	static int min_val = 1; //(1,0),(0,0)인 경우도 생각해보면 1이 가장 적절한 초기값입니다.
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = Integer.parseInt(sc.nextLine());
		s = new food[N];
		answer = new food[N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(sc.nextLine()," ");
			s[i] = new food(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())); 
		}
		subset(0);
		System.out.println(min_val);
	}
	
	public static void subset(int depth) {
    	
		if(depth == N) {
			int S_sum = 1;
			int B_sum = 0;
			
			for (int i = 0; i < N; i++) {
				S_sum*=answer[i].S;
				B_sum+=answer[i].B;
			}
            // 재료를 하나도 사용하지 않은 경우
			if(S_sum == 1 && B_sum == 0)return;
			
			min_val = Math.min(min_val, Math.abs(S_sum-B_sum));
			
			return;
		}
		
        //depth번째 값을 선택합니다.
		answer[depth] = s[depth];
		subset(depth+1);
		
        //depth번째 값을 선택하지 않습니다.
		answer[depth] = new food(1,0);
		subset(depth+1);
		
	}
}

class food{
	int S;
	int B;
	public food(int S , int B) {
		this.S = S;
		this.B = B;
	}
	@Override
	public String toString() {
		return "food [S=" + S + ", B=" + B + "]";
	}
}