티스토리 뷰

 

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

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

 

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

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

그럼 N개의 버거 중

1) 현재 버거를 먹을때

2) 현재 버거를 안먹을때

 

두개를 비교해주면 된다

 

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

 

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

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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] != -1return 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));
        }
    }
}
 
 
 

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

[SWEA] 7793. 오! 나의 여신님  (0) 2020.03.09
[SWEA] 7396 종구의 딸 이름 짓기  (0) 2020.03.06
[SWEA] 5684 운동  (0) 2020.03.05
[SWEA] 7988 내전 경기  (0) 2020.03.04
[SWEA] 8275 햄스터  (0) 2020.03.04
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함