[SWEA] 5215 : 햄버거 다이어트

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT 

SW Expert Academy

비슷한 유형의 문제를 많이 풀었어서 쉽게 푼 문제이다. 

 

내 코드

메모리 : 20776

실행시간 : 171 ms

코드길이 : 1540 B

 

[내 코드]

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

public class Solution {
	static int N;
	static int L;
	static int[] grade;
	static int[] kcal;
	//가장 높은 점수
	static int result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			//제한 칼로리
			L = Integer.parseInt(st.nextToken());
			//점수
			grade = new int[N];
			kcal = new int[N];
			boolean[] selected = new boolean[N];
			
			result = 0;
			
			for(int n = 0; n < N; n++) {
				st = new StringTokenizer(br.readLine());
				grade[n] = Integer.parseInt(st.nextToken());
				kcal[n] = Integer.parseInt(st.nextToken());
			}
			
			for(int n = 0; n < N; n++) {
				selected[n] = true;
				findCombi(n, kcal[n], grade[n], selected);
			}
			
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	//필수로 들어가는 재료의 index, 현재까지의 kcal, 현재까지의 점수, 선택한 재료들
	public static void findCombi(int startIndex, int cntKcal, int cntGrade, boolean[] selected) {
		//현재 칼로리가 제한보다 낮거나 같으면
		if(cntKcal <= L) {
			//더 높은 점수로 결과 바꿔줌
			result = Math.max(result, cntGrade);
		}
		else
			return;
		
		for(int i = startIndex + 1; i < N; i++) {
			if(!selected[i]) {
				selected[i] = true;
				findCombi(i, cntKcal + kcal[i], cntGrade + grade[i], selected);
				selected[i] = false;
			}
		}
	}
}