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

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

✏️ 문제 풀이

• 부분집합을 이용하여 재료를 사용할 수 있는 모든 상황을 고려하였다.
• LinkedList를 이용하여 {S,B}의 값을 넣어주었다.
• isSelected 배열을 이용하여 부분집합을 생성하였고, 재료선택 케이스마다 sum,mul을 계산해주어 절대값을 이용하여 최소값을 계속 비교해주었다.

 

✏️ 소스코드

package com.ssafy.baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main_S1_2961_손은성 {

	static LinkedList<int[]> ingre = new LinkedList<int[]>();
	static int N;
	static boolean isSelected[];
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		isSelected = new boolean[N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			ingre.add(new int[] { S, B });
		}
		subset(0);
		System.out.println(min);
	}

	// 부분집합 함수
	static void subset(int cnt) {
		int sum = 0;
		int mul = 1;
		int falseCnt = 0;
		if (cnt == N) {
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) {
					mul *= ingre.get(i)[0];
					sum += ingre.get(i)[1];
				} else
					falseCnt++;
			}
			if (falseCnt != N) { // 공집합 일 때 계산 X
				min = Math.min(min, Math.abs(mul - sum));
			}

			return;
		}
		isSelected[cnt] = true;
		subset(cnt + 1);
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}

 

✅ 후기

• 도영이 칼 일주일 압수.