[SWEA] 햄버거 다이어트

안녕하세요!
이번 포스팅에서는 어제 풀어본 햄버거 다이어트 문제에 대해서 알아보겠습니다~

---

문제

요약
제한 칼로리 내에서 먹을 수 있는 햄버거의 재료들의 선호도 점수를 더해 가장 큰 값을 리턴합니다.

처음 생각한 방법

문제 안에서 재료의 조합 이라는 말을 보고 단순하게 조합으로 풀었습니다.
근데 계속 오류가 나서 뭐가 문제일까.. 하면서 삽질하고 있었습니다.

두번째로 생각한 방법

조합으로 계속 문제를 틀려서 다시 문제를 제대로 읽었더니 이건 조합이 아니고 부분집합을 구하는 문제였던 것을 깨닫게 되었습니다.
그래서 재료들의 부분집합 중에서 제한 칼로리를 넘지 않고, 가장 선호도 점수가 높은 것을 리턴했더니 성공했어요!

코드 설명

static int max_score, N, L;
static int[][] ingredients;

우선 최대 점수를 저장할 max_score 와 입력 값으로 들어오는 N , L , 그리고 재료들의 점수와 칼로리를 저장할 ingredients 를 static 변수로 설정합니다.
부분 집합 함수를 따로 만들었기 때문에, static 으로 선언해 주었습니다.

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

    for (int t = 1; t <= T; t++) {
        sb.append("#" + t + " ");

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        max_score = 0;
        ingredients = new int[N][2];

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine(), " ");
            ingredients[n] = new int[]{ Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
        }

        subset(0, 0, 0);
        sb.append(max_score + "\n");
    }
    System.out.println(sb);
}

메인 함수는 위와 같습니다.
입 / 출력은 BufferedReader 와 StringTokenizer 를 활용했습니다.
입력 값으로 들어오는 T , N , L , 재료들을 차례대로 변수에 넣어줍니다.

private static void subset(int index, int score, int calorie) {
    if (calorie > L) return;
    if (calorie < L) max_score = (max_score < score)? score: max_score;
    if (index == N) return;

    subset(index+1, score+ingredients[index][0], calorie+ingredients[index][1]);
    subset(index+1, score, calorie);
}

부분 집합을 구현한 subset 메소드는 위와 같습니다.
부분 집합을 구현할 때, 배열의 index 에 해당하는 데이터를 포함하거나 포함하지 않거나 두 가지 경우로 재귀 함수를 호출합니다.

만약 여태까지 재료들의 calorie 의 합이 L 보다 크다면 유효하지 않은 부분 집합이므로 return 합니다.
마찬가지로index 가 N 이라면 모든 재료를 확인한 것이므로 return 합니다.

재료를 하나씩 선택하거나 선택하지 않으면서 그 때의 calorie 가 max_score 인지 확인하고, max_score 을 업데이트 해줍니다.

전체 코드

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

public class Solution {
    static int max_score, N, L;
    static int[][] ingredients;

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

        for (int t = 1; t <= T; t++) {
            sb.append("#" + t + " ");

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
            max_score = 0;
            ingredients = new int[N][2];

            for (int n = 0; n < N; n++) {
                st = new StringTokenizer(br.readLine(), " ");
                ingredients[n] = new int[]{ Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
            }

            subset(0, 0, 0);
            sb.append(max_score + "\n");
        }
        System.out.println(sb);
    }

    private static void subset(int index, int score, int calorie) {
        if (calorie > L) return;
        if (calorie < L) max_score = (max_score < score)? score: max_score;
        if (index == N) return;

        subset(index+1, score+ingredients[index][0], calorie+ingredients[index][1]);
        subset(index+1, score, calorie);
    }
}

---

마무리

전반적으로 SW Expert Academy 문제들은 시간과 메모리가 여유있는 편이라서 재귀로 알고리즘을 구현했음에도 큰 어려움 없이 통과되었습니다.
이 문제를 풀면서 다시 한번 문제를 꼼꼼히 읽어야겠다고 생각하면서.. 포스팅을 마치겠습니다!

감사합니다 :)