[SWEA] 햄버거 다이어트

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

부분 집합을 사용해 풀면 된다.

 

차례대로 햄버거 재료의 정보를 ingredientScore와 ingredientCal에 입력받는다. (ingredientScore[i]는 i번째 재료의 점수, ingredientCal[i]는 i번째 재료의 칼로리)

그리고, 재귀를 사용해 부분 집합 메서드를 작성한다.

나는 powerSet이라는 메서드에 매개변수로 int cnt, int score, int cal를 받았다.

cnt는 재료 cnt개까지의 부분집합을 의미한다. (cnt가 2라면, 2 인덱스까지 부분집합에 넣을지 말지 결정한 것)

score는 부분 집합의 원소들의 score 합을 의미하고,  cal은 부분 집합의 원소들의 칼로리 합을 의미한다.

 

먼저, 재귀로 부분 집합을 구하는 방법은, 예를 들어 { 1, 2, 3 } 으로 부분집합을 구하고 싶으면

1이 포함 or 포함 X / 2가 포함 or 포함 X / 3이 포함 or 포함 X 이므로 위 배열의 부분집합의 개수는 2^3 = 8이다.

이 공식을 활용해 powerSet 메소드를 작성하면 된다.

 

<powerSet 메소드>

[기저 조건]

단, 문제에서 재료들의 칼로리 합이 L을 넘기면 안되므로, 기저 조건에  cal > L일 경우, return을 추가한다.

cal <= L일 경우, 현재까지의 부분집합을 이루는 재료들이 햄버거를 만들 수 있다는 뜻이므로, score와 maxScore을 비교해서 score가 더 크다면, maxScore에 대입한다.

cnt가 N일 경우, 모든 부분집합을 다 만들어봤다는 뜻이므로 return한다.

 

[재귀]

재료를 선택하는 경우 : powerSet(cnt + 1, score + ingredientScore[cnt],  cal + ingredientCal[cnt]) 호출

재료를 선택하지 않는 경우 : powerSet(cnt + 1, score, cal) 호출

 

코드

package swea;

// 햄버거 다이어트 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=%ED%96%84%EB%B2%84%EA%B1%B0+%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

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

public class SWEA_5215 {
	
	private static int[] ingredientScore;
	private static int[] ingredientCal;
	private static int maxScore;
	private static int N, L;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			// input
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			ingredientScore = new int[N];
			ingredientCal = new int[N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				
				ingredientScore[i] = Integer.parseInt(st.nextToken());
				ingredientCal[i] = Integer.parseInt(st.nextToken());
			}
			
			// solve
			maxScore = 0;
			powerSet(0, 0, 0);
			
			bw.write("#" + tc + " " + maxScore);
			bw.newLine();
		}

		bw.flush();
		bw.close();
	}

	// 부분집합
	/**
	 * 	재료 index			0	 1    2	   3	4
	 * ingredientScore = { 100, 300, 250, 500, 400 };
	 * ingredientCal = { 200, 500, 300, 1000, 400 };
	 */
	private static void powerSet(int cnt, int score, int cal) {
		if (cal > L)
			return;
		
		if (cal <= L)
			maxScore = Math.max(maxScore, score);
		
		if (cnt == N)
			return;
		
		// 부분집합 활용
		powerSet(cnt + 1, score + ingredientScore[cnt], cal + ingredientCal[cnt]); // 재료 선택
		powerSet(cnt + 1, score, cal); // 재료 선택 안함
	
	}

}