5215. 햄버거 다이어트

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

SW Expert Academy

 

문제 해석

민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다.

민기는 이 가게에서 자신이 먹었던 햄버거의 재료에 대한 맛을 자신의 오랜 경험을 통해 점수를 매겨놓았다.

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때

민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정됩니다.

같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없습니다.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어집니다.

 

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한된 칼로리를 나타내는 N과 L이 공백으로 구분되어 주어집니다.

 

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 T(i), K(i)가 공백으로 구분되어 주어집니다.

 

제약조건

1 ≤ N ≤ 20

1 ≤ L ≤ 10 ^4

1 ≤ Ti ≤ 10^3

1 ≤ Ki ≤ 10^3

 

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 주어진 제한 칼로리 이하의 조합 중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력한다.

 

문제 풀이 전 설계

제한된 칼로리 이하의 조합중에 가장 맛에 대한 점수가 높은 햅 버거의 점수를 출력해야 합니다.

 

맛은 좋으면서 칼로리가 낮을수록 좋습니다.

 

맛/칼로리 의 값으로 표현하면 다음과 같습니다.

100/ 200 = 0.5

300/500 = 0.4

250/300 = 0.83

500/1000 = 0.5

400/400 = 1.0

 

탐욕 법 (매 순간 가장 맛/칼로리가 높은 것을 우선적으로 선택)을 고려해보았으나 칼로리에 따라 조합된 경우가 달라져 이를 충족하지 않을 수 있어서 동작하지 않을 것 같습니다.

 

따라서 완전탐색을 조합을 사용하기로 생각했습니다.

조합의 경우에는 2^n의 시간 복잡도를 가집니다.

 

코드

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

class IngredientInfo {
	int taste = 0;
	int calorie = 0;
}

public class HamburgerDiet {

	static IngredientInfo[] ingredients;
	static int limitedCalorie;
	static int numberOfIngredient;	
	static int mostDeliciousScore;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			mostDeliciousScore = 0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			numberOfIngredient = Integer.parseInt(st.nextToken());
			limitedCalorie = Integer.parseInt(st.nextToken());

			ingredients = new IngredientInfo[numberOfIngredient];

			for (int i = 0; i < numberOfIngredient; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				ingredients[i] = new IngredientInfo();
				ingredients[i].taste = Integer.parseInt(st.nextToken());
				ingredients[i].calorie = Integer.parseInt(st.nextToken());
			}
			
			getMaxIngredient(0, 0, 0);
			System.out.println("#" +t +" "+mostDeliciousScore);
		}
		br.close();

	}



	static void getMaxIngredient(int idx, int curPoint, int curCal) {
		if (curCal > limitedCalorie) {
			return;
		}
		if (curPoint > mostDeliciousScore) {
			mostDeliciousScore = curPoint;
		}
		if (idx == numberOfIngredient) {
			return;
		}
		
		getMaxIngredient(idx + 1, curPoint + ingredients[idx].taste, curCal + ingredients[idx].calorie);
		getMaxIngredient(idx + 1, curPoint, curCal);

	}

}