SWEA 5215 - 햄버거 다이어트

Java

5215 번 - 햄버거 다이어트

문제

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,
민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

접근 방법

DFS를 통하여 부분 집합을 구한다.
부분 집합이란, [1,2,3,4,5]라는 원소가 있으면
[1], [2], [3], [4], [5], [1,2], [1,3] ~ [1,2,3,4,5] 와 같이 부분 집합을 구하는 것이며,
이를 이용하여 재료의 부분 집합을 구하여 그 재료들의 칼로리 합이 제한 조건 보다 낮으면 그 재료들의 점수 합을 구한다.
점수 합들의 최댓값을 구하여 출력한다.

구현

ArrayList와 Pair를 이용하여 각 재료들의 정보를 저장한다.

DFS를 통하여 n개의 재료들을 뽑을지 말지 정한다.
이를 sel[] 배열을 통하여 나타내며, sel 인덱스는 ArrayList의 인덱스와 일치시켜 만약 sel[i]가 true이면 이 인덱스를 통해 ArrayList에 접근하여 재료 정보를 얻는다.

위 과정을 설명하면,

1. DFS(0,0)으로 첫번째 재료부터 탐색을 한다.
2. 현재 재료를 선택하는 경우와 선택하지 않는 경우를 각각 호출한다.
3. 만약 재료를 선택하는 경우, 현재 재료의 칼로리를 합하여 다음 DFS의 인자로 넘겨준다
4. 총 칼로리의 합이 L을 넘어가면, 더 이상 탐색할 가치가 없으므로 종료한다.
5. n개의 재료의 선택 유무를 다 확인하면, 이제 선택 된 재료들의 점수를 합한다.
6. 합한 점수의 최댓값을 갱신한다

코드

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

class Solution {
	static boolean sel[];
	static int n, l, result = 0;
	static ArrayList<Pair> mtr;// material
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int idx = 1; idx <= tc; idx++) {
    		result = 0;
    		mtr = new ArrayList<>(); 
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		l = stoi(stk.nextToken());
    		
			// 재료 추가
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			mtr.add(new Pair(stoi(stk.nextToken()), stoi(stk.nextToken())));
    		}
    		
    		sel = new boolean[n];
    		DFS(0,0);
    		
    		System.out.println("#" + idx + " " + result);
    	}
    	br.close();
	}
	
	static void DFS(int lv, int Cal) {
		// 조기 종료 조건. 제한 칼로리 보다 선택한 재료들의 칼로리가 높으면 종료
		if(Cal > l) {
			return;
		}
		if(lv == n) {	// n개의 재료 선택 유무가 완료되었을 시
			int sumC = 0;
			for(int i = 0; i < n; i++){
				if(sel[i])
					sumC += mtr.get(i).a;	// 선택한 재료들의 점수 합을 구한다.
			}
			result = Math.max(result, sumC);	// 점수 합이 기존 합보다 클 시
			return;
		}
		
		sel[lv] = true;			// 현재 재료 하나를 선택 하였을 시
		DFS(lv + 1, Cal + mtr.get(lv).b);	// 선택한 재료의 칼로리를 추가하여 다음 재료 선택 유무 호출
		sel[lv] = false;		// 재료를 선택하지 않음
		DFS(lv + 1, Cal);		// 선택하지 않은 재료이므로, 칼로리 추가 없이 다음 재료 선택 유무 확인
		
	}
	static class Pair {
		public int a;		// 점수
		public int b;		// 칼로리
		Pair(int a, int b){
			this.a = a;
			this.b = b;
		}
		@Override		// Pair가 정상적으로 동작하는지 확인하는 toString
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(a).append(" ").append(b);
			return sb.toString();
		}
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

각 테스트 케이스를 시도하는 반복문 초기에 ArrayList와 Result를 초기화 해주지 않아 3번이나 틀렸다.
이를 주의깊게 볼 필요가 있다.

개선할 점

없