[JAVA]SWExpert_5215_햄버거다이어트

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=%ED%96%84%EB%B2%84%EA%B1%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

 

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

public class Solution_5215{
 
	static int T;
	static int N,L;
	static int flavor[],cal[];
	static boolean isSelected[];
	static int maxScore=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine()); //테스트 케이스 갯수
		StringTokenizer st;
		for(int t=1;t<=T;t++) {
			maxScore = 0;
			
			st = new StringTokenizer(br.readLine());	
			N = Integer.parseInt(st.nextToken()); //재료의 수
			L = Integer.parseInt(st.nextToken()); //제한 칼로리
			flavor = new int[N];
			cal= new int[N];
			isSelected = new boolean[N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				flavor[i] = Integer.parseInt(st.nextToken());
				cal[i] = Integer.parseInt(st.nextToken());
			}
			
			Subset(0);
			System.out.println("#"+t+" "+maxScore);
		}

	}

	static void Subset(int cnt) {
		if(cnt == N) {
			int sumCal = 0;
			int sumFla = 0;
			for(int i=0;i<N;i++) {
				if(isSelected[i]) {
					sumCal += cal[i];
					sumFla += flavor[i];
				}
			}
			if(sumCal<=L && sumFla>maxScore)
				maxScore = sumFla;
			return;
		}
	
			isSelected[cnt] = true;
			Subset(cnt+1);
			isSelected[cnt] = false;
			Subset(cnt+1);
	}
}