[SWEA] D3 5215 햄버거 다이어트 자바(Java)

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT

SW Expert Academy

 

풀이

문제 이해를 했지만 DP는 풀이할 때마다 너무 어렵다..

현재 음식을 선택한 경우와 선택하지 않고 다음 음식으로 이동하는 경우 재귀 호출을 사용해 풀이했다.

 

풀이 코드

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

public class Solution {
	public static int n, l, max;
	public static int arr[][];
	public static int result = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			n = sc.nextInt();
			l = sc.nextInt();
			arr = new int[n][2];
			max = 0;

			for (int i = 0; i < n; i++) {
				arr[i][0] = sc.nextInt();
				arr[i][1] = sc.nextInt();
			}

			search(0, 0, 0);
			System.out.println("#" + test_case + " " + max);
		}
	}

	public static void search(int idx, int taste, int cal) {
		if (cal > l) return;
		if (cal <= l) max = Math.max(max, taste);
		if (idx == n) return;
		
		// 현재 음식을 선택한 경우
		search(idx + 1, taste + arr[idx][0], cal + arr[idx][1]);

		// 현재 음식을 선택하지 않고 다음 음식으로 이동
		search(idx + 1, taste, cal);
	}
}