[SWEA] 5215 햄버거 다이어트 - JAVA

1. 문제

SW Expert Academy

---

2. 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class D3_5215_햄버거다이어트 {
    static int N, L;
    static int[][] ingredients;
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
 
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
 
            //입력
            StringTokenizer st = new StringTokenizer(in.readLine());
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
 
            ingredients = new int[N][2]; //0 :  맛 점수, 1 : 칼로리
 
            for (int n = 0; n < N; n++) {
                st = new StringTokenizer(in.readLine());
                ingredients[n][0] = Integer.parseInt(st.nextToken());
                ingredients[n][1] = Integer.parseInt(st.nextToken());
            }
 
            //탐색+출력
            sb.append(calcTaste(0, 0, 0)).append("\n");
        }
 
        System.out.print(sb);
    }
 
 
    public static int calcTaste(int cal, int score, int n) {
        if (cal > L) return 0;
        if (n == N) return score;
 
        return Math.max(calcTaste(cal + ingredients[n][1], score + ingredients[n][0], n + 1),
                calcTaste(cal, score, n + 1));
    }
}

1. Base: 현재 칼로리가>한계칼로리이면 0 리턴하고 끝, 현재 인덱스가 재료의 수와 같다면 끝낸다.

2. Recursive: 현재 인덱스의 재료를 더한 것, 더하지 않은 것을 각각 구해서 둘 중 최대값을 리턴한다.

---

3. 결과

틀린 코드 ▽ (checked는 방문여부 확인 배열이다)

public static int calcTaste(int score,int taste, int n) {
    if(n==N) return taste;
    if(score+ingredients[n][1]>L) return taste;
 
    checked[n] = true;
    taste += ingredients[n][0];
    score += ingredients[n][1];
 
    int maxTaste = taste;
    for(int i=0;i<N;i++) {
        if(checked[i]) continue;
        maxTaste = Math.max(maxTaste,calcTaste(score,taste,i));
    }
 
    checked[n] = false;
 
    return maxTaste;
}