[코딩 테스트 RUN] SWEA RUN : 5215. 햄버거 다이어트

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[SW Expert Academy] 5215. 햄버거 다이어트

 

SW Expert Academy

 

대표적인 DP 문제.

그 중에서도 역산하는 DP문제이다.

 

나를 웃게 만든 댓글들

 

민기의 제한 열량 칼로리는 L이기 때문에, 여기서 역산을 한다. 세 개의 배열이 준비되어 있어야 하는데, 하나는 재료의 점수를 담을 배열, 하나는 재료의 칼로리를 담을 배열, 마지막으로 햄버거를 쌓을 배열이다.

이 햄버거를 쌓을 배열의 경우 제한 칼로리 L + 1을 넣고, 각 재료마다 햄버거를 쌓아나가야 한다.

 

            for(int i = 0; i < N; i++){
                //이번 재료를 투하
                int kal = calories[i];
                int score = scores[i];
            }

 

이번 재료를 이런 형태로 넣으면, 해당 칼로리와 스코어를 저장한다.

 

for(int j = L; j >= kal; j--){
   arr[j] = Math.max(arr[j], arr[j - kal] + score);
}

 

(i 내에 있는 for문이다)

 

이 부분이 DP의 핵심적인 부분이다.

arr[j](쌓은 햄버거)를 Math.max하고 있는데, 지금까지 쌓은 조합과, 지금에서 kal을 뺀(즉, 재료이 재료를 얹기 전의 칼로리의 최고점수) 쌓은 햄버거에서 지금 score(지금 재료의 점수)를 얹는 것을 비교하는 것이다.

여기서 L에서 역산해나간다는 것이 포인트. 0에서부터 쌓아올리면 재료를 중복해서 쓸 수 있다(재료는 한번에 한번 제한이 있다), 제한 칼로리를 지키기에는 이쪽이 더 효율적이다. arr[L]은 처음에 0이고, - 해나가면 결국 재료 본연의 칼로리에 자신의 점수를 적립하게 된다. 이러한 것을 반복해나가다보면 햄버거쌓기의 최대 점수를 얻게 되고, 결국엔 arr[L]은 최대 점수의 결과가 나오게 되는 것이다.

 

 

정답

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

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            //테스트 케이스 시작
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 재료의 수
            int N = Integer.parseInt(st.nextToken());
            // 제한 칼로리
            int L = Integer.parseInt(st.nextToken());

            int[] scores = new int[N];
            int[] calories = new int[N];

            for(int i = 0; i < N; i++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                //민기의 점수, 칼로리
                scores[i] = Integer.parseInt(st2.nextToken());
                calories[i] = Integer.parseInt(st2.nextToken());
            }
            // 점수 및 칼로리 추가 완료
            int[] arr = new int[L + 1];

            for(int i = 0; i < N; i++){
                //이번 재료를 투하
                int kal = calories[i];
                int score = scores[i];

                for(int j = L; j >= kal; j--){
                    arr[j] = Math.max(arr[j], arr[j - kal] + score);
                }

            }
            System.out.printf("#%d %d%n",test_case, arr[L]);

        }

    }
}