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

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

SW Expert Academy

---

풀이

package edu.ssafy.im.SWEA.D3.No5215;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    int n, l; // 재료의 수, 제한 칼로리
    int[] happy, score; // 각 재료의 맛에 대한 점수와 칼로리
    int ans; // 가장 맛에 대한 점수가 높은 햄버거의 점수

    public static void main(String[] args) throws IOException {
        new Solution().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine());

        for (int t = 1; t <= testCase; t++) {
            String input = br.readLine();
            StringTokenizer st = new StringTokenizer(input);
            n = Integer.parseInt(st.nextToken()); // 재료의 수
            l = Integer.parseInt(st.nextToken()); // 제한 칼로리

            happy = new int[n]; // 재료의 맛에 대한 점수 배열 초기화
            score = new int[n]; // 재료의 칼로리 배열 초기화

            // 재료의 맛에 대한 점수와 칼로리 입력
            for (int i = 0; i < n; i++) {
                input = br.readLine();
                st = new StringTokenizer(input);
                happy[i] = Integer.parseInt(st.nextToken());
                score[i] = Integer.parseInt(st.nextToken());
            }

            ans = 0; // 결과 초기화
            recursion(0, 0, 0); // 재귀 함수 호출하여 햄버거 조합 생성
            sb.append("#").append(t).append(" ").append(ans).append("\n"); // 결과 출력
        }
        System.out.println(sb);
    }

    private void recursion(int i, int happySum, int scoreSum) {
        // 기본 파트: 제한 칼로리를 넘어가면 종료
        if (scoreSum > l)
            return;
        // 기본 파트: 현재 맛에 대한 점수가 최대일 때 결과 업데이트
        if (happySum > ans)
            ans = happySum;
        // 기본 파트: 모든 재료를 고려했을 때 종료
        if (i == n)
            return;

        // 재귀 파트
        // 현재 재료를 선택한 경우
        recursion(i + 1, happySum + happy[i], scoreSum + score[i]);
        // 현재 재료를 선택하지 않은 경우
        recursion(i + 1, happySum, scoreSum);
    }
}