[SWEA][Java] 5215. 햄버거 다이어트

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT

SW Expert Academy

 

문제 이해

제한된 칼로리 내에서 맛 점수를 최대화하는 재료의 조합을 찾는 문제이다.

맛 점수와 칼로리를 가진 N개의 재료가 있다.

이 중에서 일부를 선택해서 총 칼로리가 L 이하인 조합 중에서 맛 점수의 합이 최대가 되는 경우를 구한다.

 

문제 풀이

📁 재료 정보 저장: 각 재료는 맛 점수와 칼로리를 갖고 있으며, 이를 Pair 클래스로 만들어 List에 저장한다.

 

💡  백트래킹을 이용한 조합 탐색

: 가지치기(pruning)를 통해 칼로리를 초과하는 경우 조기 종료하여 불필요한 탐색을 줄인다.

• 현재 인덱스 idx, 누적 맛 점수 tasteSum, 누적 칼로리 calSum을 인자로 재귀 호출한다.
• 현재 재료를 선택하는 경우와 선택하지 않는 경우로 나누어 재귀 호출한다.
• 누적 칼로리가 제한 칼로리 l을 초과하면 해당 조합은 버린다.
• 모든 재료를 탐색했다면 (idx == list.size()), 현재 조합의 맛 점수를 최대값으로 갱신한다.

 

코드

import java.io.*;
import java.util.*;

public class Solution {

    static class Pair {
        int taste;
        int calories;

        Pair(int taste, int calories) {
            this.taste = taste;
            this.calories = calories;
        }
    }

    static List<Pair> list = new ArrayList<>();
    static int l = 0;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            ans = 0;
            list.clear();

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            l = Integer.parseInt(st.nextToken());

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int taste = Integer.parseInt(st.nextToken());
                int cal = Integer.parseInt(st.nextToken());
                list.add(new Pair(taste, cal));
            }

            backtracking(0, 0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void backtracking(int idx, int tasteSum, int calSum) {
        if (calSum > l) return;
        if (idx == list.size()) {
            ans = Math.max(ans, tasteSum);
            return;
        }

        backtracking(idx + 1, tasteSum + list.get(idx).taste, calSum + list.get(idx).calories);
        backtracking(idx + 1, tasteSum, calSum);
    }
}