[SWEA] 5215 햄버거 다이어트

 

다이어트를 하기위해 최적의 햄버거를 찾는 최고의 문제다

실생활에서 우리가 마주칠수있는 현실적인 문제 굿

 

일단 이 문제는 DP를 이용해서 풀 수 있다

내가 L 칼로리 이하를 먹어야만한다

그럼 N개의 버거 중

1) 현재 버거를 먹을때

2) 현재 버거를 안먹을때

 

두개를 비교해주면 된다

 

이 때 현재 버거를 먹기위해선 칼로리(sum+b[pos])가 L 이하여야 한다!

 

그럼 그 값들 중 최대값을 찾아보자!

 

소스코드

import java.util.Scanner;
 
public class Solution {
    public static int[][] d;
    public static int[] a,b;
    public static int t,n,l;
    
    public static int solve(int pos,int sum) {
        if(pos==n) return 0;
        if(d[pos][sum] != -1) return d[pos][sum];
        d[pos][sum]= solve(pos+1,sum);
        if(b[pos]+sum<=l) d[pos][sum] = Math.max(d[pos][sum], a[pos]+solve(pos+1,sum+b[pos]));
        return d[pos][sum];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        
        for(int tc=1;tc<=t;tc++) {
            n = sc.nextInt();
            l = sc.nextInt();
            
            a = new int[n];
            b = new int[n];
            d = new int[n][l+1];
            
            for(int i=0;i<n;i++) {
                for(int j=0;j<=l;j++) d[i][j]=-1;
                a[i]=sc.nextInt();
                b[i]=sc.nextInt();
            }
            
            System.out.println("#"+tc+" "+solve(0,0));
        }
    }
}