[swea] [Java] 5215. 햄버거 다이어트

[문제링크]

 

주어진 만족도, 칼로리 쌍을 이용하여 최대 칼로리 이하에서 최대의 만족도를 구하는 문제이다

 

✨IDEA : 

낮은 칼로리 순으로 정렬 후 합쳐볼까..

높은 만족도 순으로 정렬 후 합쳐볼까... 어떻게 조합을 해볼까 고민이 될수도 있지만 그냥 모든 조합들을 다 생각하면 된다

즉, 해당 쌍을 포함한 것 안포함한 것의 모든 경우를 계산한 뒤 주어진 칼로리 제한 안에서 가장 높은 만족도를 가지는 것을 출력!

 

처음 buger메소드를 구현할 때는 cnt가 주어진 K번까지 부분집합 경우를 체크하고 최댓값을 체크했으나 그럴필요 없이 재귀함수가 돌아가는 중 제한된 칼로리 보다 높아지면 바로 짤라주면 더 효율적인 풀이가 될 수 있다

package SWEA;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.StringTokenizer;

public class 햄버거 {
	static int T, N, limit, answer;
	static int [][] arr; //칼로리, 만족도를 담을 배열
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static void buger(int cnt, int good, int cal) {
		if(cal > limit) // 주어진 칼로리 제한보다 높아지면 바로 컽!
			return;
		if(cnt == N) {
			answer = Math.max(answer, good);
			return;
		}
		
		buger(cnt + 1, good, cal);
		buger(cnt + 1, good + arr[cnt][0], cal + arr[cnt][1]);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new FileReader("./input.txt"));
		
		T = Integer.parseInt(input.readLine());
		for(int tc = 1; tc <= T; tc++) {
			tokens = new StringTokenizer(input.readLine());
			N = Integer.parseInt(tokens.nextToken());
			limit = Integer.parseInt(tokens.nextToken());
			
			arr = new int[N][2];
			
			for(int i = 0; i < N; i++) {
				tokens = new StringTokenizer(input.readLine());
				arr[i][0] = Integer.parseInt(tokens.nextToken());
				arr[i][1] = Integer.parseInt(tokens.nextToken());
			}
			
			answer = Integer.MIN_VALUE;
			buger(0, 0, 0);
			
			output.append(String.format("#%s %d\n", tc, answer));
		}
		System.out.println(output);
		
		
	}

}