5215 햄버거 다이어트

햄버거 다이어트 URL

Solution

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

public class SW5215 {
    static int[] score;
    static int[] kcal;
    static int N, L, answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
            score = new int[N];
            kcal = new int[N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                score[i] = Integer.parseInt(st.nextToken());
                kcal[i] = Integer.parseInt(st.nextToken());
            }
            answer = 0;
            dfs(0, 0, 0);
            System.out.println("#" + t + " " + answer);
        }
    }

    static void dfs(int idx, int scr, int kal) {
        if (kal > L) {
            return;
        }

        if (idx == N) {
            answer = Math.max(answer, scr);
            return;
        }
        //재료를 추가할 경우
        dfs(idx + 1, scr + score[idx], kal + kcal[idx]);
        //재료를 추가하지 않고 건너띄는 경우
        dfs(idx + 1, scr, kal);
    }
}

배운점

먼저 문제를 읽고 먼저 든 생각은 완전탐색이구나를 생각하였다.

그리고 나서 어떻게 풀어야할지 고민했지만 Map함수를 사용하는 방법이 떠올랐고 풀다보니 리스트도 필요하고 반복문도 추가되어 비 효율적인 방식이라고 생각이들었다.

결국 풀이를 보게 되었고 부분집합의 합을 구하는 문제와 유사하다는 것을 알게 되었다.

풀이

1. 점수와 칼로리를 담을 배열을 각각 생성한다.

2. dfs 탐색에서 매개변수로 0부터 인덱스를 늘리기위해 idx를 0으로 넘기고 매번 점수와 칼로리를 계산하기 위해 src, kal 변수를 넘겼다.

   3-1. dfs 탐색의 종료조건으로 kal값이 L을 초과할 때.

   3-2. idx가 N과 일치할때 (N과 일치해야 N-1까지 계산 결과가 담긴다)

3. 재료를 추가할 경우와 재료를 추가하지 않고 건너띄는 경우를 각각 재귀 호출한다.