[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_PowerSet {
    int n, l, ans;
    int[] happy, score;

    public static void main(String[] args) throws IOException {
        new Solution_PowerSet().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; // 최종 결과 초기화
            powerSet(0, new boolean[n]); // 부분집합 구하기

            // 결과 출력
            sb.append("#").append(t).append(" ").append(ans).append("\n");
        }
        System.out.println(sb);
    }

    private void powerSet(int idx, boolean[] sel) {
        // basis part
        if (idx == n) { // 모든 재료를 선택했을 때
            int happySum = 0, scoreSum = 0;
            // 선택된 재료의 맛과 칼로리 계산
            for (int i = 0; i < sel.length; i++) {
                if(sel[i]) {
                    happySum += happy[i];
                    scoreSum += score[i];
                }
            }
            // 제한 칼로리를 초과하면 종료
            if (scoreSum > l)
                return;
            // 현재까지의 최대 맛 갱신
            if (happySum > ans)
                ans = happySum;
            return;
        }

        // inductive part
        // 현재 재료를 선택한 경우
        sel[idx] = true;
        powerSet(idx + 1, sel);
        // 현재 재료를 선택하지 않은 경우
        sel[idx] = false;
        powerSet(idx + 1, sel);
    }
}