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

Java

2961 번 - 도영이가 만든 맛있는 음식

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

접근 방법

DFS를 이용해 부분 집합을 구한다.
뽑힌 원소들의 신맛의 곱과 쓴맛의 합을 구한다.
2개의 차이를 구한 뒤, 그 중 최소 값을 출력한다.

구현

DFS의 부분집합을 구하는 방법으로 생각하였다.
sel배열은 각 원소를 선택하였는가의 여부를 나타낸다.
n개 만큼의 원소를 선택/비선택 하였다면, sel배열의 각 인덱스가 true인 값들에 해당하는 신맛, 쓴맛 정보를 가져와 곱/합을 구한다.

주의해야할 것은, 모든 원소를 선택하지 않는 경우가 있는데 이를 방지해야한다.
모든 원소를 선택하지 않았다면 쓴맛의 합이 0이 되는데, 문제 조건에서 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수라고 하였으므로 합이 0이 될 수 없으므로 조건문으로 이를 방지한다.

코드

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

public class Main {
	static int n, result = 987654321;
	static boolean[] sel;
	static int[][] sb;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk; 
    	n = stoi(br.readLine());
    	sb = new int[n][2];			// 쓴맛과 신맛의 정보가 들어있는 배열
    	sel = new boolean[n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		sb[i][0] = stoi(stk.nextToken());
    		sb[i][1] = stoi(stk.nextToken());
    	}
    	
    	DFS(0);
    	
    	System.out.println(result);
    	br.close();
    }
    
    static void DFS(int lv) {
		// N개의 원소들이 선택여부를 확인 하였을 때
    	if(lv == n){
    		int sSum = 1, bSum = 0;
    		for(int i = 0; i < n; i++) {
				// 선택이 된 원소들만 계산
    			if(sel[i]) {
    				sSum *= sb[i][0];
    				bSum += sb[i][1];
    			}
    		}
    		int cal = Math.abs(sSum - bSum);
    		if(bSum != 0)	// 부분 집합 중, 하나도 안 뽑힌 경우를 방지
    			result = Math.min(result, cal);
    		return;
    	}
		// 0 ~ N-1번째의 원소를 선택하거나, 선택하지 않는다.
    	sel[lv] = true;	
    	DFS(lv + 1);
    	sel[lv] = false;
    	DFS(lv + 1);
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

부분 집합을 응용하는 문제였다.
막상 구현하려니 막혀, 다음에는 바로 구현이 가능하도록 공부하자

개선할 점

없