[SWEA JAVA] 5215. 햄버거 다이어트

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

SW Expert Academy

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int T, N, L, ans = 0;
	public static int[] S, K;
	public static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			S = new int[N + 1];
			K = new int[N + 1];
			dp = new int[N + 1][L + 1];

			for (int i = 1; i <= N; i++) {
				st = new StringTokenizer(br.readLine());
				S[i] = Integer.parseInt(st.nextToken());
				K[i] = Integer.parseInt(st.nextToken());
			}

			for (int i = 1; i < N + 1; i++) {
				for (int j = 0; j <= L; j++) {
					if (j < K[i]) {
						dp[i][j] = dp[i - 1][j];
					} else {
						dp[i][j] = Math.max(dp[i - 1][j - K[i]] + S[i], dp[i - 1][j]);
					}
				}
			}

			ans = dp[N][L];

			System.out.println("#" + tc + " " + ans);
		}
	}
}

 

dp[N][L] 의 의미 : N번째 물건까지 가방에 담았을때 , 제한 무게가 L을 초과하지 않는 최대 가치