SWEA 5215. 햄버거 다이어트

import java.util.Scanner;
import java.io.FileInputStream;
 
class Solution
{
    static int N;
    static int L;
    static int[][] arr;
    static int answer;
 
 
    static int max;
    public static void main(String args[]) throws Exception
    {
 
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            L = sc.nextInt();
            answer = 0;
            max =0;
            arr = new int[N][2];
 
            for(int i = 0; i<N; i++){
                for(int j = 0; j<2; j++){
                    arr[i][j] = sc.nextInt();
                }
            }
            dfs(0,0);
            System.out.println("#"+ test_case+ " "+ max);
        }
    }
    public static void dfs(int index, int totalcal){
 
        for (int i = index; i < N; i++) {
            if(totalcal + arr[i][1]>L){
                continue;
            }
            totalcal += arr[i][1];
            answer += arr[i][0];
            max = Math.max(max,answer);
            dfs(i+1,totalcal);
            totalcal -= arr[i][1];
            answer -= arr[i][0];
        }
    }
}

풀이방법

L 이하의 값을 조합하여 점수가 최대가 되는 경우의 수를 찾는 문제이다.
완전탐색, 백트래킹을 이용했다.

보통 갯수를 초과했을때, return 하는 문제들이 많았는데, 이문제는 L을 초과했을때, return하는 방식으로 푼다면 이후 경우의수를 체크하지 못한다.

즉, 1,2,3,4,5 가 있을때,
1,2,3을 고르고 4에서 L을 초과해서 return한다면, 1,2,3,5인 경우의 수는 체크가 안되는 것이다.
따라서 이문제에서는 L을 초과시 return이 아닌 continue를 하여 다음 경우의 수로 넘어가 체크를 해줘야 한다.
그리고 모든 경우의 수 중 최댓값을 구하여 출력.
다른부분은 일반적인 백트래킹과 동일하다.

후기

익숙하지 않은 유형이어서 알아채는데 시간이 많이 걸렸다.