햄버거 다이어트

1. 문제 접근 및 아이디어

이 문제는 주어진 재료들을 사용하거나, 사용하지 않거나를 결정하여 제한 칼로리 내에서 최대 점수를 뽑아내는 것이 핵심입니다.

1. 입력 데이터 구조화
   • 각 재료의 점수와 칼로리를 쌍으로 묶어 저장합니다.
2. 선택의 기로
   • 각 재료를 포함할 것인가? 아니면 포함하지 않을 것인가?라는 두 가지 선택지를 바탕으로 모든 경우의 수를 고려합니다.
3. 상태 전이
   • 재료를 선택하면 점수와 칼로리가 합산되고, 선택하지 않으면 이전까지의 합계를 그대로 가져갑니다.
4. 조건 검사
   • 모든 재료를 다 확인했거나, 중간에 칼로리가 L을 초과하면 탐색을 종료합니다.

2. 필요 개념 및 알고리즘

1. DFS/백트래킹
   • 재료의 수 N이 최대 20개로 매우 작습니다.
   • 모든 경우의 수를 고려하면 2^20(약 100만) 정도로 완전 탐색이 가능합니다.

3. 어려웠던 점

1. 재귀 함수 구현
   • 재귀 함수의 흐름을 머리속으로 그리는 것이 어려웠습니다.
   • 현재까지의 점수와 칼로리를 매개변수로 넘겨주는 방식을 구현하기 힘들었습니다.

4. 코드 풀이

4.1 선택의 기로

// 선택
dfs(level + 1, scoreSum + score, kcalSum + kcal);

// 미선택
dfs(level + 1, scoreSum, kcalSum);

• 각 재료를 포함할 것인가? 아니면 포함하지 않을 것인가?라는 두 가지 선택지를 바탕으로 모든 경우의 수를 고려합니다.

4.2 조건 검사

// 가지치기
if (kcalSum > L)
	return;

// 종료 조건
if (level == N) {
	result = Math.max(result, scoreSum);
	return;
}

• 모든 재료를 다 확인했거나, 중간에 칼로리가 L을 초과하면 탐색을 종료합니다.

4.3 DFS 함수 코드

static void dfs(int level, int scoreSum, int kcalSum) {

	// 가지치기
	if (kcalSum > L)
		return;

	// 종료 조건
	if (level == N) {
	    result = Math.max(result, scoreSum);
		return;
	}

	// 현재 점수와 칼로리
	int score = list.get(level)[0];
	int kcal = list.get(level)[1];

	// 선택
	dfs(level + 1, scoreSum + score, kcalSum + kcal);

	// 미선택
	dfs(level + 1, scoreSum, kcalSum);

}

4.4 전체 코드

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

public class Solution_D3_5215_햄버거다이어트 {

	static int N, L; // 재료의 수, 제한 칼로리
	static ArrayList<int[]> list; // 재료의 점수와 칼로리 리스트
	static int result; // 가장 높은 햄버거의 점수

	public static void main(String[] args) throws NumberFormatException, IOException {

		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine().trim());

		// tc 수행
		for (int tc = 1; tc <= T; tc++) {

			// 재료의 수, 제한 칼로리 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());

			// 가장 높은 점수, 리스트 초기화
			result = 0;
			list = new ArrayList<>();

			// 재료의 맛의 점수, 칼로리 입력
			for (int i = 0; i < N; i++) {

				st = new StringTokenizer(br.readLine());

				int t = Integer.parseInt(st.nextToken());
				int k = Integer.parseInt(st.nextToken());

				// 맛의 점수와 칼로리 리스트에 추가
				list.add(new int[] { t, k });

			}

			// 처리
			dfs(0, 0, 0);

			// 출력 내용 추가
			sb.append("#" + tc + " " + result + "\n");

		} // tc 종료

		// 출력
		System.out.println(sb);

	} // 메인 종료

	static void dfs(int level, int scoreSum, int kcalSum) {

		// 가지치기
		if (kcalSum > L)

			return;

		// 종료 조건
		if (level == N) {

			result = Math.max(result, scoreSum);

			return;

		}

		// 현재 점수와 칼로리
		int score = list.get(level)[0];
		int kcal = list.get(level)[1];

		// 선택
		dfs(level + 1, scoreSum + score, kcalSum + kcal);

		// 미선택
		dfs(level + 1, scoreSum, kcalSum);

	}

}