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

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=1&&&&&&&&&&

SW Expert Academy

 

 

 

- 주어진 칼로리 제한을 초과하지 않고 가장 높은 점수를 주는 재료의 조합을 찾아야 한다. 

- 칼로리 제한으로 달성할 수 있는 최대 점수를 나타내는 db 배열 memo를 만든다. 

- 처음에는 아무런 재료도 없이 0으로 초기화하면 dp 점수는 0이다. 

 

- 각 칼로리 제한 'j'에 대해 memo[j]값을 현재 값과 memo[j-calories[i]]+score[i]값중 큰 값으로 업데이트

-  -> 현재 재료를 포함하는 경우를 고려한 것

 

memo[j] : 현재 칼로리 제한 'j'에서 얻을 수 있는 최대 점수

calries[i] : i번째 재료의 칼로리 값

scores[i] : i번째 재료의 점수 값

 

<현재 재료를 포함하는 경우>

 

memo[j - calories[i]] :  현재 재료를 포함하기 전의 상태에서의 최대 점수 

memo[j - calories[i]] + scores[i]  : 현재 재료를 포함했을 때의 점수 

 

<현재 재료를 포함하지 않는 경우>

 

memo[j] : 현재 재료를 포함하지 않는 상태에서의 최대 점수 

 -> 이전에 계산된, 현재 칼로리 제한 j에서의 최대점수 

 

Math.max(memo[j], memo[j - calories[i]] + scores[i])

- 현재 재료를  포함하는 경우와 포함하지 않는 경우 중 최대 점수를 선택한다. 

- 이는 두 값 중 더 큰 값을 선택하여 memo[j]에 저장한다. 

- 즉, memo[j]는 현재 칼로리 제한 j에서의 최대 점수를 항상 유지한다. 

 

 

정답 

 

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int t=1; t<=T; t++) {
			
			int N = sc.nextInt(); //재료의 수
			int L = sc.nextInt(); //제한 칼로리
			//주어진 제한  칼로리 이하의 조합중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력
			
			int scores[] = new int[N];
			int calories[] = new int[N];
			
			for(int i=0; i<N; i++)
			{
				scores[i] = sc.nextInt();
				calories[i] = sc.nextInt();
				
			}
			
			//각 칼로리 제한에서의 최대 점수를 저장할 db 배열 생성
			int memo[] = new int[L+1];
			
			
			//현재 재료를 고려하여 dp 배열 업데이트
			for(int i=0; i<N; i++)
			{
				for(int j=L; j>=calories[i]; j--)
				{
					//현재 칼로리 제한에서 최대 점수를 반영하도록 dp 배열 업데이트
					
					memo[j] = Math.max(memo[j],memo[j-calories[i]]+scores[i]);
				}
			}
			
			int answer = memo[L];
			
			
			System.out.printf("#%d %d\n", t, answer);
		}
	}
}