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

[문제 바로가기]

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

 

💡풀이💡

요리를 할 때 N개의 재료들을 사용하거나 / 사용하지 않거나 해서 신맛과 쓴맛의 차이가 최소인 값을 찾는 문제이다.

• 가능한 재료들의 모든 집합을 구해야 하기 때문에 부분 집합

 

1. 입력 값

재료마다 신맛과 쓴맛의 값을 저장해야 했기 때문에 2차원 배열로 재료의 값을 저장했다.

그리고 어떤 재료가 선택 됐는지 알기 위해 boolean 1차원 배열을 생성했다.

	static int N;
	static int[][] flavors;
	static boolean[] v;
	static int min=1000000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		flavors = new int[N][2];
		v = new boolean[N];
		
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			flavors[i][0] = Integer.parseInt(st.nextToken()); // 신맛
			flavors[i][1] = Integer.parseInt(st.nextToken()); // 쓴맛
		}
	}

 

 

2. 부분 집합 구하기

1. 해당 재료를 사용하는 경우
2. 해당 재료를 사용하지 않는 경우로 나눠서 진행

📌 놓쳤었던 부분!

• 문제에서 보면 재료는 적어도 하나 사용해야 한다고 나와있다.
• 부분 집합을 구하게 되면 아무것도 선택되지 않은 공집합도 포함이 되는데 이때를 걸러내지 않아서 틀렸었다.

static void subset(int cnt) {
	if(cnt == N) {
		long f1 = 1; // 신맛
		long f2 = 0; // 쓴맛
		for(int i=0; i<N; i++) {
			if(v[i]) {
				f1 *= flavors[i][0];
				f2 += flavors[i][1];
			}
		}
		if(f1 == 1 && f2 == 0) return; // 아무것도 선택되지 않으면 return
		min = Math.min(min, Math.abs(f1-f2));
		return;
	}
		
	v[cnt] = true; // cnt번 재료를 사용할 때
	subset(cnt+1);
	v[cnt] = false; // cnt번 재료를 사용하지 않을 때
	subset(cnt+1);
}

 

전체 코드 

1) 부분 집합이 완성 됐을 때, 각 요리에 사용된 신맛, 쓴맛 계산하기

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

public class B2961 {
	static int N;
	static int[][] flavors;
	static boolean[] v;
	static long min=1000000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		flavors = new int[N][2];
		v = new boolean[N];
		
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			flavors[i][0] = Integer.parseInt(st.nextToken()); // 신맛
			flavors[i][1] = Integer.parseInt(st.nextToken()); // 쓴맛
		}
		
		subset(0);
		System.out.println(min);
	}
	
	static void subset(int cnt) {
		if(cnt == N) {
			int f1 = 1; // 신맛
			int f2 = 0; // 쓴맛
			for(int i=0; i<N; i++) {
				if(v[i]) {
					f1 *= flavors[i][0];
					f2 += flavors[i][1];
				}
			}
			if(f1 == 1 && f2 == 0) return;
			min = Math.min(min, Math.abs(f1-f2));
			return;
		}
		
		v[cnt] = true;
		subset(cnt+1);
		v[cnt] = false;
		subset(cnt+1);
	}

}

 

 

2) 부분 집합을 구하는 재귀 함수의 매개변수로 각 재료의 신맛, 쓴맛 값 전달하기

package backjoon;

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

public class B2961 {
	static int N;
	static int[][] flavors;
	static boolean[] v;
	static int min=1000000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		flavors = new int[N][2];
		v = new boolean[N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			flavors[i][0] = Integer.parseInt(st.nextToken()); // 신맛
			flavors[i][1] = Integer.parseInt(st.nextToken()); // 쓴맛
		}
		

		subset(0, 1, 0);
		System.out.println(min);
	}
	static void subset(int cnt, int f1, int f2) {
		if(cnt == N) {
            		if(f1 == 1 && f2 == 0) return; // 공집합일 때(아무것도 선택 안 됐을 때) 처리
			min = Math.min(min, Math.abs(f1-f2));
			return;
		}
		
		v[cnt] = true;
		subset(cnt+1, f1*flavors[cnt][0], f2 +flavors[cnt][1]);
		v[cnt] = false;
		subset(cnt+1, f1, f2);
	}

}

 

정리

1. 문제를 보면 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000(10억)보다 작은 양의 정수이다. 라고 되어있다. 그래서 신맛(f1), 쓴맛(f2) 계산하는 변수, 둘의 차의 최솟값을 저장하는 min이 int의 범위를 벗어나는 줄 알고 long으로 선언했었다. 근데 int의 범위가 20억이라고 굳이 long으로 안 해도 된다고 페어가 알려주셨다ㅎㅎㅎ 페어 짱짱맨👍👍😎😎
   난... int 범위가 2억인줄 알았다...

2. 위에도 적었었지만 부분 집합을 구할 때는 공집합이 있을 수도 있다는 걸 까먹었다. 문제를 잘 읽어보고 부분 집합을 이      용할 때는 공집합일 때를 잘 처리해야겠다.