[백준 / Java] 2961번: 도영이가 만든 맛있는 음식 (실버2)

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2961번: 도영이가 만든 맛있는 음식 (실버2)

 

키워드

백트랙킹, 부분 집합

 

풀이 접근법

• 재료의 개수 1 ≤ N ≤ 10 ⇒ 재귀로 구할 수 있다.
• 백트랙킹과 달리, 원소가 위치하는 자리는 고려하지 않는다. 선택/비선택 여부만 신경쓴다. (selected 배열)
• 어떤 원소를 선택하지 않았다면 다음 재귀로 해당 원소를 합산하지 않고 넘긴다.
• 모든 재료를 사용해서 요리를 만들었을 때, 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수 ⇒ 10^9 ≤ 2^32
• 부분 집합을 구하고 그에 맞는 신맛과 쓴맛의 수치를 계산한다. 그런데 문제에서 공집합은 허용하지 않았으므로 selected 배열이 모두 false라면 계산하지 않고 넘어가주어야 한다. (continue)

 

코드

import java.io.*;

public class Main {

	private static int minDiff = Integer.MAX_VALUE;
	private static int N;

	private static int[][] ingredients;
	private static boolean[] selected;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		ingredients = new int[N][2];
		selected = new boolean[N];

		String[] temp;
		for (int i = 0; i < N; i++) {
			temp = br.readLine().split(" ");
			ingredients[i][0] = Integer.parseInt(temp[0]);
			ingredients[i][1] = Integer.parseInt(temp[1]);
		}

		DFS(0, 1, 0);

		System.out.println(minDiff);
	}

	public static void DFS(int depth, int sour, int bitter) {
		if (depth == N) {
			if(isAllFalse()) { // 공집합은 만들지 않는다.
				return;
			}
			minDiff = Math.min(minDiff, Math.abs(sour - bitter));
			
			return;
		} 
		
		int s = ingredients[depth][0];
		int b = ingredients[depth][1];
		
		selected[depth] = true;
		DFS(depth + 1, sour * s, bitter + b);

		selected[depth] = false;
		DFS(depth + 1, sour, bitter);

		return;
	}

	private static boolean isAllFalse() {
		for(boolean b : selected) {
			if(b == true)
				return false;
		}
		return true;
	}

}

 

---

 

 

git 링크

(git 링크 첨부)