[SWEA]5215번:햄버거 다이어트(JAVA)

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

SW Expert Academy

---

• 풀이방법[알고리즘]

각 재료의 맛 점수 합을 더해가면서  제한 칼로리를 넘지않는 최대 합을 구한다. dfs를 사용하여, 순서대로 맛 점수를 더해 최대 칼로리보다 작으면서 가장 큰 값이 나오는 경우를 계산한다. 해당 재료를 넣었을 때와 넣지 않은 경우의 수를 각각 계산하여 maxScore를 리턴하면 끝!

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

public class Main{
	static int[][] food;
    static int maxScore;
    static int maxCal;
	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 k=1;k<=tc;k++){
            String[] NL  = br.readLine().split(" ");
            maxCal = Integer.parseInt(NL[1]);
            //맛 점수와 칼로리를 넣을 배열 생성
            food = new int[Integer.parseInt(NL[0])][2];
            for(int i=0;i<Integer.parseInt(NL[0]);i++){
                String[]str = br.readLine().split(" ");
                food[i][0] = Integer.parseInt(str[0]);
                food[i][1] = Integer.parseInt(str[1]);
            }

            calculate(0,0,0);
            System.out.println("#"+k+" "+maxScore);
		}//tc
	}//main
	static void calculate(int idx, int score, int cal){
    	if(cal>maxcal){
        	return
        }else if(score>maxScore){
        	maxScore = score;
        }
        if(idx==food.length)return;
        
       calculate(idx+1,score+food[idx][0],cal+food[idx][1]);
       calculate(idx+1,score,cal);
    }
}//class