[SW Expert Academy] - (D3)5215. 햄버거 다이어트(조합)

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

SW Expert Academy

코드

import java.util.Scanner;

public class Solution {
	static int N;	// 재료 수
	static int L;	// 제한 칼로리
	static int ans;	// 최대 점수
	static int[] score;	// 점수
	static int[] cal;	// 제한 칼로리
	
	/**
	 * @param count  - 재료수 카운트
	 * @param sum    - 최대 점수
	 * @param allCal - 칼로리 합
	 */
	public static void dfs(int count, int sumScore, int allCal) {
		/* 기저 사례: 여태 더한 칼로리량이 제한 칼로리보다 클때,*/
		if(allCal > L) {
			return;
		}
		
		/* N개의 재료까지 뽑았을경우 -> 최대 점수 비교*/
		if(count == N) {
			ans = Math.max(ans, sumScore);
			return;
		}
		
		/* 재귀호출(dfs): 재료수+1, 점수, 칼로리 합  */
		dfs(count+1, sumScore+score[count], allCal+cal[count]);
		
		/* 재료 빼기 */
		dfs(count+1, sumScore, allCal);
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int t = scan.nextInt();
		for(int tc=1; tc<=t; tc++) {
			N = scan.nextInt();	// 재료 수
			L = scan.nextInt();	// 제한 칼로리
			score = new int[N];
			cal = new int[N];
			ans = 0;
			
			for(int i=0; i<N; i++) {
				score[i] = scan.nextInt();
				cal[i] = scan.nextInt();
			}
			
			// 재료개수, 점수합, 칼로리량 0으로 Start
			dfs(0, 0, 0);
			
			System.out.println("#" + tc + " " + ans);
		}
		scan.close();
	}
}

풀이

제한된 칼로리(L) 에서 가장 높은 점수를 선택하면 된다.

부분집합의 합을 구하는 문제와 비슷하다.

각 원소에 대해 해당 재료를 선택하는 경우, 선택하지 않는 경우를

재귀함수를 통해 반복적으로 호출하며 최적의 해를 찾아야 한다.

이 문제에서는 두가지 종료조건이 있다.

 

 - 재료를 선택하면서 더해진 칼로리의 합이 제한된 칼로리를 초과한 경우

     - allCal > L

 - N번째 재료까지 모두 탐색한 경우

     - count == N : 최대 점수를 비교한다(max함수)

 

재귀 호출부분에서는, 탐색을 하며 점수의 합과 칼로리의 합을 더해가는데,

 - 재료를 선택할 경우: 재료와 점수, 칼로리를 모두 더해준다.

 - 재료를 선택하지 않는 경우: 재료만 +1(다음 재료로 넘겨주는) 해준다.

 

 

아직 순열, 조합에 대해서 정리가 안되어서 재귀 함수가 익숙하지가 않다...

빠른 시일내에 순열&조합에 대해 한번 정리를 해야겠따 ,,