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

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

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

 

 

 

 

 

배낭 문제 유형이다. 배낭 문제는 재귀를 이용한 부분집합 알고리즘을 사용한다.

 

 신맛과 쓴맛은 2차원 배열을 이용하여 저장했다.

그리고 재귀의 매개변수로 음식의 신맛과 쓴맛을 념겨줘 누적으로 계산하도록 했다.

 

음식을 넣었을 때와 안넣었을 경우. 두 가지의 경우를 재귀로 돌리도록 했다.

그러다가 N번을 다 탐색하면 차이를 구해 최솟값을 갱신하도록 했다. 이때 아무것도 안쓰는 경우는 제외해야 한다.

 

긜고 또 주의할 점은 쓴맛은 곱하기를 하므로 초기값이 0 아니라 1로 시작해야 한다.

 

 

 

 

코드

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

public class Main {
	static int N;
	static int[][] dish;
	static int min = 1000000000;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		dish = new int[N][2]; //신맛, 쓴맛
		
		for(int i =0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			dish[i][0] = Integer.parseInt(st.nextToken());
			dish[i][1] = Integer.parseInt(st.nextToken());
		}
		
		subset(0, 1, 0); //쓴 맛은 곱하기라서 1로 초기값 해야함
		
		System.out.println(min);

	}

	public static void subset(int depth, int sour, int bitter) {
		if(depth == N) {
			if(sour != 1 && bitter != 0) { //아무것도 사용 안하는 경우 제외
				int d = Math.abs(sour - bitter);
				min = Math.min(min, d);
			}
			
			return;
		}
		
		subset(depth + 1, sour * dish[depth][0], bitter + dish[depth][1]);
		subset(depth + 1, sour, bitter);
	}

}

 

 

 

 

 

 

결과