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

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

SW Expert Academy

1. 주의할 점

- 조합, DP를 통한 풀이 방법이 있지만, DP(메모아이징)를 통해 해결한다

- 시작 전, DP[][]의 값을 전부 초기화한다

 

2. 구현

- DP[Idx][Remain] 배열을 통해 해당 Idx의 위치에서 Remain만큼 남은 칼로리가 있을 때, 얻을 수 있는 가장 큰 점수를 저장한다

- Knapsack 알고리즘을 통해 해당 'Idx의 위치에 있는 재료를 추가해서 얻을 수 있는 가장 큰 점수'와 '해당 재료를 추가하지 않고 얻을 수 있는 가장 큰 점수'중에서 가장 큰 점수를 DP에 저장한다

- 계산한 값과 Result값을 비교하여 큰 값을 Result에 할당한다

 

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

public class Solution_d3_5215_햄버거다이어트 {
	
	static int num, limit,result;
	static int val[], weight[],dp[][];
	
	static int knapsack(int idx, int remain) {
		if(idx==num) return 0;
		int temp = dp[idx][remain];
		if(temp!=-1) return temp;
		if(weight[idx]<=remain) 
			temp = knapsack(idx+1,remain-weight[idx])+val[idx];
		temp = Math.max(temp, knapsack(idx+1,remain));
		result = Math.max(result, temp);
		return dp[idx][remain]=temp;	
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			num = Integer.parseInt(st.nextToken());
			limit = Integer.parseInt(st.nextToken());
			result=0;
			val = new int[num];
			weight = new int[num];
			dp = new int[num][limit+1];
			for(int i=0;i<num;i++) {
				String str = br.readLine();
				StringTokenizer st2 = new StringTokenizer(str);
				val[i] = Integer.parseInt(st2.nextToken());
				weight[i] = Integer.parseInt(st2.nextToken());
				for(int j=0;j<=limit;j++)
					dp[i][j]=-1;
			}
			knapsack(0,limit);
			System.out.println("#"+t+" "+result);
		}
	}
}