[SWEA] 5215. 햄버거 다이어트 - 부분집합

5215. 햄버거 다이어트

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

SW Expert Academy

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

// 210208 

public class Solution_D3_5215_햄버거다이어트 {
	
	static int N, L;
	static int[][] burgerArr;
	static int maxPoint; 
	// static 변수는 main에서 매번 초기화 해야 하는거 까먹지좀말자^^
	
	static void subset(int cnt, int totalCal, int totalPoint) {
		
		if (totalCal > L) {
			return;
		}
		
		if (cnt==N) {
			maxPoint = Math.max(maxPoint, totalPoint);	
			return;
		} 
		subset(cnt+1, totalCal + burgerArr[cnt][1], totalPoint + burgerArr[cnt][0]);
		subset(cnt+1, totalCal, totalPoint);

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

		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 재료수
			L = Integer.parseInt(st.nextToken()); // 제한 칼로리
			maxPoint = 0;
		
			burgerArr = new int[N][2];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				burgerArr[i][0]  = Integer.parseInt(st.nextToken()); // 점수
				burgerArr[i][1]  = Integer.parseInt(st.nextToken()); // 칼로리
			}
			
			subset(0, 0, 0);
			System.out.println("#" + tc + " " + maxPoint);
			
		}
		
		br.close();
	}

}

 

1. static 변수는 main에서 매번 초기화 하는거 잊지 좀 말자

2. 완전 탐색 (부분집합/ 조합/ 순열) 코드에 익숙해지자 많이 풀자