[SWEA / 햄버거 다이어트 / JAVA]

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 접근

재료를 썼을 때 맛에 대한 점수가 가장 높아야되고 / 재료 중복 X / 칼로리도 넘지않아야 한다.

대부분이 재귀 형태로 풀었더라

처음엔 이해가 안되서 출력을 찍으면서 과정을 보았다.

재귀 메서드 내에서 해당 인덱스에 있는 재료를 선택했을 때와 선택하지 않았을 때의 맛과 칼로리를 매 번 검사해서 칼로리가 제한 칼로리 이하라면 그 때 마다 최대값을 비교해서 저장해준다.

 

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

public class Main {
	static int N;
	static int totalKcal;
	static int[] score;
	static int[] kcal;
	static int highScore;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 재료 수
			totalKcal = Integer.parseInt(st.nextToken()); // 제한 칼로리
			
			score = new int[N]; // 점수
			kcal = new int[N]; // 칼로리
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				score[i] = Integer.parseInt(st.nextToken());
				kcal[i] = Integer.parseInt(st.nextToken());
			}
			
			highScore = 0;
			cb(0, 0, 0);
			System.out.println("#"+t+" "+ highScore);
		}
	}
	
	public static void cb(int num, int sumScore, int sumKcal) {
		
		if(sumKcal <= totalKcal) highScore = Math.max(highScore, sumScore);
		if(sumKcal > totalKcal) return;
		if(num == N) return;
		
		cb(num+1, sumScore + score[num], sumKcal+ kcal[num]); // n번 째 재료를 선택했을 경우
		cb(num+1, sumScore, sumKcal); // n번 째 재료를 선택안했을 경우
	}
}