[SW Expert Academy] 5215:햄버거다이어트 (Java) / 부분집합

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

public class Solution {
	static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int limit =0;
	static int numOfFood=0;
	static int[][] foodInfo;
	static boolean[] isSelected;
	static Queue<int[]> queue;
	static int maxNum;
	public static void main(String[] args) throws Exception {
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			input();
			maxNum = 0;
			generateSubset(0);
			System.out.printf("#%d %d\n", t, maxNum); // 높은 스코어 출
		}
	}
  
	private static void generateSubset(int cnt) {
		if(cnt == numOfFood) { // 5개를 다 돌았을 때, 
			int total =0;
			int sumOfScore =0;
			for(int i=0; i<numOfFood; i++) {
				if(isSelected[i]) { // 선택 되어있으면
					sumOfScore += foodInfo[i][0]; // 스코어 더함 
					total += foodInfo[i][1]; // 음식 칼로리 더함
					if(total>limit) return; // 만약 제한 칼로리를 넘으면 그냥 return
				}
			}
			maxNum = Math.max(maxNum, sumOfScore); // 제한 칼로리보다 낮으면서 높은 스코어를 갱신해서 저장
			return;
		}
		isSelected[cnt] = true; // 선택
		generateSubset(cnt+1);
		isSelected[cnt] = false; // 비선택
		generateSubset(cnt+1);
	}
  
	private static void input() throws Exception {
		st = new StringTokenizer(br.readLine());
		numOfFood = Integer.parseInt(st.nextToken());
		limit = Integer.parseInt(st.nextToken());
		foodInfo = new int[numOfFood][2];
		isSelected = new boolean[numOfFood];
		for(int i=0; i<numOfFood; i++) {
			st = new StringTokenizer(br.readLine());
			foodInfo[i][0] = Integer.parseInt(st.nextToken());
			foodInfo[i][1] = Integer.parseInt(st.nextToken());
		}
	}
}

 

최초 발행 날짜: 2021-02-08