SW 5215 햄버거 다이어트

문제 풀기에 앞서,

재귀함수로 설계하고 구현하는 데 어려움이 있어서 최대한 재귀함수로 구현하는 사고방식을 글로 적어 내려가면서 풀었다.

 

햄버거 다이어트

문제 설명

햄버거 재료에 대한 점수와 재료에 대한 칼로리가 주어졌을 때, 정해진 칼로리 이하의 조합 중에서 가장 선호하는 햄버거를 조합해주는 프로그램을 만드는 것이다.

 

입력

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

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한 칼로리를 나타내는 N, L(1 ≤ N ≤ 20, 1 ≤ L ≤ 104)가 공백으로 구분되어 주어진다.

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 Ti, Ki(1 ≤ Ti ≤ 103, 1 ≤ Ki ≤ 103)가 공백으로 구분되어 주어진다.

 

출력

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

 

 

분석 및 설계

점수와 칼로리를 각각 배열에 담아 인덱스로 값을 꺼내고 재귀식으로 함수를 호출해 가장 높은 점수를 체크해 출력해야될 것 같다.

 

가장 중요한 건 재귀 함수를 구현하는 것이다.

 

코드 구현

import java.util.Scanner;

public class SW5215_햄버거다이어트 {
	
	
	static int[] scores;
	static int[] calories;
	static int N, L;
	
	public static void main(String[] args) throws Exception {
		
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		
		
		for(int test_case = 1; test_case <= T; test_case++) {
			
			N = sc.nextInt();
			L = sc.nextInt();
			
			scores = new int[N];
			calories = new int[N];
			
			for (int i = 0; i < N; i++) {
				scores[i] = sc.nextInt();
				calories[i] = sc.nextInt();
			}
			
			System.out.print("#" + test_case);
			System.out.print(" " + hamburger(0, 0, 0));
			
		}
	}

	private static int hamburger(int cnt, int tSum, int lSum) {
		
		if (lSum > L) return 0;
		
		if (cnt == N) return tSum;
		
		int notTake = hamburger(cnt + 1, tSum, lSum);
		int take = hamburger(cnt + 1, tSum + scores[cnt], lSum + calories[cnt]);
		
		return Math.max(notTake, take);
	}
}

아무 것도 고르지 않는 경우까지 갔다가 올라오면서 하나씩 고른 경우와 고르지 않은 경우를 비교하면서 가장 큰 값을 리턴한다.