[SWEA 5215번] 햄버거 다이어트 with Java

guswls·2024년 5월 16일
0

알고리즘

목록 보기
38/39
post-custom-banner

문제




코드


1. 부분집합 문제로 해결하기(dfs)

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

class Solution {
	static final int SCORE = 0;
	static final int CALORIE = 1;

	static int N;
	static int L;
	static int max;
	static int[][] arr;

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 재료 개수
			L = Integer.parseInt(st.nextToken()); // 제한 칼로리
			max = 0;

			arr = new int[N][2];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				arr[i][SCORE] = Integer.parseInt(st.nextToken());
				arr[i][CALORIE] = Integer.parseInt(st.nextToken());
			}

			dfs(0, 0, 0);

			sb.append(String.format("#%d %d\n", t + 1, max));
		}
		System.out.println(sb);
	}

	static void dfs(int count, int score, int calorie) {		
		if (count >= N) {
			if (calorie <= L) {
				max = Math.max(score, max);
			}
			return;
		}
		
		// 선택하는 경우
		dfs(count + 1, score + arr[count][SCORE], calorie + arr[count][CALORIE]);

		// 선택하지 않은 경우
		dfs(count + 1, score, calorie);
	}
}

2. dp로 해결하기

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

class Solution {
	static final int SCORE = 0;
	static final int CALORIE = 1;

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 재료 개수
			int L = Integer.parseInt(st.nextToken()); // 제한 칼로리

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

			int[][] dp = new int[N + 1][L + 1];
			for (int i = 1; i < N + 1; i++) {
				for (int j = 1; j < L + 1; j++) {
					if (arr[i][CALORIE] > j) {
						dp[i][j] = dp[i - 1][j];
					} else {
						dp[i][j] = Math.max(dp[i - 1][j], arr[i][SCORE] + dp[i - 1][j - arr[i][CALORIE]]);
					}
				}
			}

			sb.append(String.format("#%d %d\n", t + 1, dp[N][L]));
		}
		System.out.println(sb);
	}
}


문제 이해


  • 전형적인 knapsack문제이다.
  • 여기서는 점수칼로리가 주어졌을 때 칼로리L 이하인 경우에서 가장 높은 점수를 구하는 문제이다.


풀이 방법


  • 이 문제를 보면 결국 선택문제를 의미한다.
  • 어떤 한 재료를 선택하는 경우와 선택하지 않을 경우 두 상황으로 문제를 만들어 생각해야 한다.
  • dpdfs모두 현재 시점에서 선택할 것이냐, 말것이냐를 따지는 문제이다.
  • 공통적으로 재료의 개수를 N개라고 했을 때 arr[N][2]배열에 점수와 칼로리를 저장한다.

DFS풀이

  • 현재 선택한 재료의 인덱스, 칼로리합, 점수합을 파라미터로 가지는 dfs메서드를 만든다.
  • 종료 조건은 현재 재료의 인덱스가 N, 즉 모든 재료를 탐색했을 때이다.
  • 위 조건을 만족하면서 칼로리합이 L보다 작은 경우, 최대값을 갱신하고, 만족하지 않으면 return한다.
  • 재귀호출은 두파트로 나눠진다. 현재 시점에서 해당 재료를 선택하는 경우, 해당 재료의 칼로리와 점수만큼을 더해서 재호출한다.
  • 현재 시점에서 해당 재료를 선택하지 않는 경우, count만 갱신하고 나머지 파라미터는 갱신하지 않는다.

DP풀이

  • 0-1 배낭문제의 전형적인 풀이를 사용하면 된다.

  • dp[재료 개수][칼로리 제한]형태로 dp테이블을 준비한다.

  • 이중 for문을 순회하며 dp테이블에 현재 칼로리(j)에서의 최대 점수를 채워 나간다.

  • 만약 현재 칼로리(j)보다 재료의 칼로리가 더 크다면 선택할 수 없다. 따라서 이전의 선택dp[i-1][j]로 테이블을 갱신한다.

  • 만약 재료를 선택할 수 있다면, 재료를 넣는 경우와 넣지 않는 경우에 대해서 더 큰값을 넣어야 한다. 그에 대한 점화식은 아래와 같다.

    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-arr[i][CALORIE])+arr[i][SCORE]

  • 점화식이 어렵긴하지만, 동적 테이블을 간략하게 그려보면 현재 칼로리(j)상황에서 새로운 값을 넣냐, 이전 값을 선택하냐에 대한 상황을 유추할 수 있다.



핵심 포인트


  • 문제를 딱 마주쳤을 때 결국 선택 문제, dp혹은 dfs로 모든 선택에 대한 경우를 구해야된다는 것을 알아 차려야 된다.
  • dfs의 경우는 코드가 직관적이기 때문에 간단히 이해할 수 있으나, dp는 선택하는 경우를 구하기 매우 까다롭다.
  • 이럴 때는 간단하게나마 표를 그리면 쉽게 접근할 수 있다.


보완할 점 / 느낀 점


  • 처음 문제를 봤을 때, 단순히 칼로리와 점수로 알맞게 정렬한 후 그리디하게 선택하면 풀 수 있을 것이라 생각했는데, 오해였다.
  • 이상한 낌새를 보고 문제 댓글창을 확인하니, knapsack문제라는 것을 알 수 있었고 바로 찾아봐서 문제를 해결했다.
  • dp가 매번 문제를 풀 때마다 점화식이 헷갈려서 어려웠었는데, 표를 그리면서 생각해보니 이전거를 선택하는 경우와 현재꺼를 더하는 경우에 대한 이해가 직관적으로 됐었다.
  • 일단 계속 코드를 보며 어느정도의 암기는 해두어야겠다.
  • 만약 dp 풀이가 안떠오르면, dfs로라도 풀 수 있게 대비해둬야겠다.


참고자료


profile
안녕하세요
post-custom-banner

0개의 댓글