SW Expert Academy - 5215번(햄버거 다이어트)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=5215&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

• 처음 코드

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

public class Solution {

    private static int T, N, L, ingredients[], calories[], calorie, ingredient;
    private static boolean[] isSelected;
    private static int result;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(reader.readLine());
        int problemNum = 1;

        while (T-- > 0) {
            result = 0;
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            N = Integer.parseInt(tokenizer.nextToken());
            L = Integer.parseInt(tokenizer.nextToken());

            isSelected = new boolean[N];
            ingredients = new int[N];
            calories = new int[N];
            int count = N;
            int index = 0;

            while (count-- > 0) {
                tokenizer = new StringTokenizer(reader.readLine());
                ingredients[index] = Integer.parseInt(tokenizer.nextToken());
                calories[index++] = Integer.parseInt(tokenizer.nextToken());
            }

            subset(0);

            sb.append("#").append(problemNum++).append(" ");
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    private static void subset(int index) {
        if (index == N) {
            for (int i = 0; i < N; i++) {
                if (isSelected[i]) {
                    ingredient += ingredients[i];
                    calorie += calories[i];
                }
            }

            if (calorie <= L && ingredient > result) {
                result = ingredient;
            }
            ingredient = 0;
            calorie = 0;

            return;
        }

        isSelected[index] = true;
        subset(index + 1);
        isSelected[index] = false;
        subset(index + 1);
    }

}

• 부분집합을 통해 구현하였으나, 시간이 너무 오래 걸렸다.
• 다른 분의 도움으로 "조합"을 이용하여 제대로 구현하였다. 모든 가능한 합의 경우의 수를 생각하되, 지정된 조건을 만족하는 값들만을 남겨둔다. 순열, 조합, 부분집합이 익숙치 않아 아직 적용이 힘들다...

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

public class Solution {

    private static int T, N, L, ingredients[], calories[], calorie, ingredient;
    private static boolean[] isSelected;
    private static int result;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(reader.readLine());
        int problemNum = 1;

        while (T-- > 0) {
            result = 0;
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            N = Integer.parseInt(tokenizer.nextToken());
            L = Integer.parseInt(tokenizer.nextToken());

            isSelected = new boolean[N];
            ingredients = new int[N];
            calories = new int[N];
            int count = N;
            int index = 0;

            while (count-- > 0) {
                tokenizer = new StringTokenizer(reader.readLine());
                ingredients[index] = Integer.parseInt(tokenizer.nextToken());
                calories[index++] = Integer.parseInt(tokenizer.nextToken());
            }

            combination(0, 0, 0);

            sb.append("#").append(problemNum++).append(" ");
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    private static void combination(int start, int calorie, int ingredient) {
        if (calorie > L) return;
        if (ingredient > result) result = ingredient;

        for (int i = start; i < N; i++) {
            combination(i + 1, calorie + calories[i], ingredient + ingredients[i]);
        }
    }

}