[SW Expert] 5215. 햄버거 다이어트

1) 생각

주어진 칼로리의 값을 넘지 않도록 더해가면서 맛의 만족도가 최대가 되는 값을 구하자. 재료의 수가 최대 20개로 많지 않으므로 주어진 시간인 Java 8초를 생각하면 모든 조건을 따져봐돠 충분히 풀 수 있을것이다.

2) 방안

재귀를 통한 DFS 방식을 통해 쭉욱 살펴보면서 그 값이 더해졌을 경우, 더해지지 않았을 경우를 따지면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
    static int n,l;
    static int[] score, kalory;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            l = Integer.parseInt(st.nextToken());
            score = new int[n];
            kalory = new int[n];
            for(int j=0;j<n;j++) {
                st = new StringTokenizer(br.readLine());
                score[j] = Integer.parseInt(st.nextToken());
                kalory[j] = Integer.parseInt(st.nextToken());
            }
            maxScore = 0;
            check = new boolean[n];
             
            dfs(0,0,0);
            System.out.println("#"+i+" "+maxScore);
        }
    }
     
    static int maxScore;
    static boolean[] check;
    private static void dfs(int idx,int s,int k) {
        if(k>l) return;
        if(idx==n) {
            maxScore = Math.max(maxScore, s);
            return;
        }
        dfs(idx+1,s+score[idx],k+kalory[idx]);
        dfs(idx+1,s,k);
    }
}