[문제] SWEA 5215번 햄버거 다이어트

* swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=5215&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

내 풀이

 

1. 첫번째 풀이

부분집합으로 완전 탐색해서 풀었다.

 

public class SWEA_5215 {
	static int N;	// 재료 수
	static int L;	// 제한 칼로리
	static int maxScore=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(in.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			String[] s = in.readLine().split(" ");
			N = Integer.parseInt(s[0]);	
			L = Integer.parseInt(s[1]);	
			
			int[][] hamburger = new int[N][2];
			
			for(int i=0;i<N;i++) {
				String[] s2 = in.readLine().split(" ");
				hamburger[i][0] = Integer.parseInt(s2[0]);	// 점수
				hamburger[i][1] = Integer.parseInt(s2[1]);	// 칼로리
			}
			maxScore = 0;
			subset(0,new boolean[N], hamburger);
			sb.append("#").append(tc).append(" ").append(maxScore).append("\n");
		}
		System.out.print(sb);
	}
	static void subset(int cnt, boolean[] isSelected, int[][] hamburger) {
		if(cnt == N) {
			int sumCal = 0;
			int sumScore = 0;
			
			for(int i=0;i<N;i++) {
				if(isSelected[i]) {
					sumCal += hamburger[i][1];
				}
			}
			if(sumCal <= L) {
				for(int i=0;i<N;i++) {
					if(isSelected[i]) {
						sumScore += hamburger[i][0];
					}
				}
			}
			maxScore = Math.max(sumScore, maxScore);
			return;
		}
		isSelected[cnt] = true;
		subset(cnt+1, isSelected,hamburger);
		isSelected[cnt] = false;
		subset(cnt+1, isSelected,hamburger);
		
		
	}
}