[SW expert Academy] SWEA 5215번 햄버거 다이어트 자바(Java)

[D3] 햄버거 다이어트 - 5215

문제 링크

성능 요약

메모리: 23,716 KB, 시간: 199 ms, 코드길이: 1,114 Bytes

제출 일자

2023-10-25 14:11

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

import java.util.*;
 
class Solution
{
    static int result = 0;
    static int[][] ingredients;
    static boolean[] visit;
    static int n,l;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
        for(int tc = 1; tc <= T; tc++)
        {
            result = -1;
            n = sc.nextInt();
            l = sc.nextInt();
            ingredients = new int[n][2];           
            visit = new boolean[n];
            for(int i = 0; i < n; i++){
                ingredients[i][0] = sc.nextInt();
                ingredients[i][1] = sc.nextInt();
            }
            combination(0,0,0);
             
            System.out.println("#" + tc + " " + result);
        }
    }
    private static void combination(int depth,int curCal, int score){
        for(int i = depth; i < ingredients.length; i++){
            if(curCal + ingredients[i][1] <= l){
                combination(i+1,curCal + ingredients[i][1], score + ingredients[i][0]);
            }
        }
        result = Math.max(result, score);
    }
}

값을 들고 다니면서 계산 가능한 부분만 recursion 해줬다.

-> 그냥 recursion 해주고 칼로리 상한선 넘으면 return 해주는게 가독성이 더 좋다.

import java.util.*;

class Solution
{
    static int result = 0;
    static int[][] ingredients;
    static boolean[] visit;
    static int n,l;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            result = -1;
            n = sc.nextInt();
            l = sc.nextInt();
            ingredients = new int[n][2];           
            visit = new boolean[n];
            for(int i = 0; i < n; i++){
                ingredients[i][0] = sc.nextInt();
                ingredients[i][1] = sc.nextInt();
            }
			combination(0,0,0);
            
            System.out.println("#" + tc + " " + result);
		}
	}
    private static void combination(int depth,int curCal, int score){
        if(curCal > l){
            return;
        }
        if(depth == n){
            result = Math.max(result , score);
            return;
        }
        combination(depth+1,curCal + ingredients[depth][1], score + ingredients[depth][0]);
        combination(depth+1,curCal,score);
    }
}