[SWEA] JAVA - 5215 햄버거 다이어트

주어진 햄버거 정보에서 어떤 햄버거들을 선택했을때 최대 칼로리 이하이면서 최대 만족도인지를 찾는 문제이다. 선택할수있는 햄버거들의 조합을 구한뒤 최대 만족도를 가지는 햄버거의 조합을 찾아야한다.

 

재귀함수를 사용해서 풀었는데 이 함수에서 파라미터로 전달해야할것은 몇번째 햄버거를 선택할것인지를 결정하는 인덱스, 현재까지 선택한 햄버거의 만족도 합, 현재까지 선택한 햄버거의 칼로리합이다.

 

1. idx 번째 햄버거를 선택 할 수 있다면(idx번 햄버거 칼로리와 이전까지 저장된 햄버거 칼로리를 더했을때 최대 칼로리를 넘지 않는다면) idx를 선택하거나 선택하지 않거나 두가지 경우로 분기한다.

2. idx 번 햄버거를 선택 할 수 없다면 다음 idx 햄버거를 고르러 간다.

3. 모든 햄버거를 다 탐색했을때이거나 현재까지 저장된 칼로리가 정해진 칼로리와 같아질때 return한다.

 

package com.ssafy.off;

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

public class SWEA_5215_햄버거다이어트 {
	/**
	 * 가장 선호하는 햄버거 조합 && 칼로리 이하
	 * (같은 재료를 여러번 사용할수없다.) 
	 */
	static int N;
	static int Kalorie;
	static int answer;
	static int info[][];
	//
	public static int solve(int idx, int score, int kalorie) {
		if (idx == N || kalorie >= Kalorie) {
			return score;
		}
		else {
			//idx 선택할수있음
			if(kalorie + info[idx][1] <= Kalorie) {
				answer = Math.max(solve(idx+1, score + info[idx][0], kalorie + info[idx][1]), solve(idx+1, score, kalorie));
			}else {
				answer = solve(idx+1, score, kalorie);
			}
		}
		return answer;
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			
			String[] data = br.readLine().split(" ");
			
			N = Integer.parseInt(data[0]);
			Kalorie = Integer.parseInt(data[1]);
			info = new int[N][2]; //맛(0),칼로리(1) 정보 배열
			answer = -1;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				info[i][0] = Integer.parseInt(st.nextToken()); 
				info[i][1] = Integer.parseInt(st.nextToken());
			}
			answer = solve(0, 0, 0);
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
		System.out.print(sb);

	}

}