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

[문제 바로가기]👇

SW Expert Academy

 

💡풀이💡

햄버거 재료의 맛 점수와 제한 칼로리가 주어졌을 때 재료를 조합해 만들 수 있는 가장 높은 맛 점수 구하기

 

문제에서 알 수 있는 정보

1. 햄버거의 선호도 = 재료들의 맛 점수의 합 → 순서가 없음
2.같은 재료를 여러 번 사용할 수 x → 중복 안됨
3.칼로리 제한 외 햄버거 조합의 제한은 x(특정 개수 이상 재료를 사용 x)
>> 따라서 부분 집합!

 

 

1. 입력 받기

i번째 재료의 맛 점수와 칼로리를 data 배열의 0번, 1번 인덱스에 저장해서 사용

	static int N, L, max;
	static int[][] data;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 햄버거 재료 개수
			L = Integer.parseInt(st.nextToken()); // 제한 칼로리
			data = new int[N][2]; // 맛 점수 , 칼로리
			max = 0;
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				data[i][0] = Integer.parseInt(st.nextToken());
				data[i][1] = Integer.parseInt(st.nextToken());
			}
		}
		br.close();
	}

 

 

2. 햄버거 재료 선택하기(부분 집합 만들기)

재료를 선택해 햄버거를 만들 때, 제한 칼로리 이상으로 가면

안되기 때문에 제한 칼로리 이하인 것만 맛 점수를 계산하도록 함

 

매개변수로 재료의 칼로리와 맛 점수를 같이 넘겨서

어떤 요소가 사용되었는지 확인하는 boolean[] 배열을 사용 하지 않았음

static void subs(int cnt, int cal, int fSum) {
		if(cal > L) return;
		if(cnt == N) {
			// 맛 점수 계산
			max = Math.max(max, fSum);
			return;
		}
		
		subs(cnt+1, cal+data[cnt][1], fSum + data[cnt][0]); // 재료 선택 했을 때
		subs(cnt+1, cal, fSum); // 재료 선택 안 했을 때
}

 

3. 전체 코드

package ps_0215;

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

public class SW5215 {
	static int N, L, max;
	static int[][] data;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			data = new int[N][2]; // 맛 점수 , 칼로리
			max = 0;
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				data[i][0] = Integer.parseInt(st.nextToken());
				data[i][1] = Integer.parseInt(st.nextToken());
			}
			
			subs(0,0, 0);
			sb.append("#").append(tc).append(" ").append(max).append("\\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	static void subs(int cnt, int cal, int fSum) {
		if(cal > L) return;
		if(cnt == N) {
			// 맛 점수 계산
			max = Math.max(max, fSum);
			return;
		}
		
		subs(cnt+1, cal+data[cnt][1], fSum + data[cnt][0]); // 재료 선택 했을 때
		subs(cnt+1, cal, fSum); // 재료 선택 안 했을 때
	}
}

 

 

4. 정리

🙄🙄🙄🙄
처음에는 칼로리만 매개변수로 넘기고 맛 점수는 boolean[]을 사용해서
부분 집합이 완성 되었을 때 다시 계산을 해줬다.

실행 속도 차이가 다른 분들이랑 차이가 너무 나서 맛 점수도 매개변수로 넘겼다.
왜 처음부터 두 개 다 안 넘기고 하나만 했을까?ㅎㅎ..

위가 칼로리, 맛 점수 모두 매개변수로 넘긴 것 , 아래가 칼로리만 매개변수로 넘긴 것