[SWEA]5215번 햄버거 다이어트(JAVA)

0. 문제 링크

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

SW Expert Academy

 

1. 문제 설명

1) 재료 N개와 제한 칼로리 L이 주어짐

2) 재료 N개로 L 이하의 조합 중에서 가장 맛이 높은 햄버거 조합 찾기

 

2. 입출력

// input
1
5 1000
100 200
300 500
250 300
500 1000
400 400

// output
#1 750

 

3. 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class swea5215 {
	static int ans = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수
		
		for(int t = 1; t <= T; t++) {
			ans = 0; // 맛 점수가 높은 햄버거 변수 값 초기화
			
			// 1. 입력
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 재료의 수
			int L = Integer.parseInt(st.nextToken()); // 제한 칼로리
			
			int[][] map = new int[N][2]; // 점수, 칼로리
			for(int n = 0; n < N; n++) {
				st = new StringTokenizer(br.readLine());
				map[n][0] = Integer.parseInt(st.nextToken()); // 점수
				map[n][1] = Integer.parseInt(st.nextToken()); // 칼로리
			}
			
			// 2. 조합
			int[] sel; // 선택한 재료
			
			for(int n = 1; n <= N; n++) { // N가지 재료 중에서 n개 뽑아서 조합하기
				recursive(map, new int[n][2], 0, 0, L);
			}
			
			// 3. 출력
			System.out.println("#" + t + " " + ans);
		}
	}
	
	// map : 원본 배열 / sel : 선택 배열 / i : 원본 배열 인덱스 / k : 선택 배열 인덱스
	private static void recursive(int[][] map, int[][] sel, int idx, int k, int L) {
		// basis part
		if(k == sel.length) { // 선택이 끝났으면
			if(arraySum(sel, 1) <= L) { // 제한 칼로리보다 낮으면
				ans = Math.max(ans, arraySum(sel, 0)); // 맛 점수 비교하기
			}
			return;
		}
		
		// inductive part
		for(int i = idx; i < map.length; i++) {
			sel[k][0] = map[i][0]; // 점수
			sel[k][1] = map[i][1]; // 칼로리
			recursive(map, sel, i+1, k+1, L);
		}
		
	}
	
	// 특정 배열의 1차원 합 구하기
	private static int arraySum(int[][] sel, int k) {
		int sum = 0;
		for(int i = 0; i < sel.length; i++) {
			sum += sel[i][k];
		}
		return sum;
	}

}

 

실행 결과

 

 

4. 회고

1) N 가지 재료 중에서 1~N개 뽑기 -> 순서 X 중복 X -> 조합

2) 조합을 다 해도 제한 칼로리 L 보다 낮은지 확인

3) 제한 칼로리 L 보다 낮아도 맛 점수가 가장 높은 조합 찾기

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea5215.java