[SWEA] 5215. 햄버거 다이어트

문제

평소 햄버거를 좋아하던 민기는 최근 부쩍 늘어난 살 때문에 걱정이 많다.

그렇다고 햄버거를 포기할 수 없었던 민기는 햄버거의 맛은 최대한 유지하면서 정해진 칼로리를 넘지 않는 햄버거를 주문하여 먹으려고 한다.

민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다.

하지만 재료는 미리 만들어서 준비해놓기 때문에 조합에 들어가는 재료를 잘라서 조합해주지는 않고, 재료를 선택하면 준비해놓은 재료를 그대로 사용하여 조합해준다. 

민기는 이 가게에서 자신이 먹었던 햄버거의 재료에 대한 맛을 자신의 오랜 경험을 통해 점수를 매겨놓았다.

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,

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

(단 여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없다.)

 

풀이방법

DFS(깊이 우선 탐색)과 Backtracking(되추적) 알고리즘을 활용해 유망한 모든 경우의 수를 구한다.

 

이를 활용해 두 가지 방법으로 풀어보았지만,

 

첫 번째 방법은 일반적인 dfs 코드로 한 정점에서 부터 시작해 모든 정점을 방문하는 코드로 작성했고,

이 경우 n이 10이상이 될 때 시간 초과가 되었다.

 

두 번째 방법은 각 노드를 포함할 경우, 포함하지 않을 경우로 모든 경우의 수를 구하는 dfs로 코드를 작성했고 시간초과가 발생하지 않았다.

 

소스코드

코드 1(시간초과)

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    static int n;
	static int m;
	static int[] a;
	static int[] b;
	static int[] v;
	static int cnt;
	static int c;
	
	public static boolean promising(int x, int sum) {
		int next = sum + b[x];
		if(next > m)
			return false;
		else
			return true;
	}
	
	public static void dfs(int x, int score, int sum) {
		v[x] = 1;
		sum += b[x];
		score += a[x];
		
		cnt = Math.max(cnt, score);
		
		for(int i = 0; i < n; i++) {
			if(v[i] == 0 && promising(i, sum)) {
				dfs(i, score, sum);
				v[i] = 0;
			}
		}
		v[x] = 0;
	}
	public static void main(String args[]) throws Exception
	{
        Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[n];
			b = new int[n];
			v = new int[n];
			cnt = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				b[i] = sc.nextInt();
			}
			
			for(int i = 0; i < n; i++) {
				dfs(i, 0, 0);
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}

 

코드 2

package samsung;

import java.util.*;

public class s_5215 {
	static int n;
	static int m;
	static int[] a;
	static int[] b;
	static int max;
	
	public static void dfs(int x, int s, int k) {
		if(k > m) {
			return;
		}
		
		if(x == n) {
			max = Math.max(s, max);
		}
		else {
			dfs(x + 1, s + a[x], k + b[x]);
			dfs(x + 1, s, k);
		}
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[n];
			b = new int[n];
			max = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				b[i] = sc.nextInt();
			}
			
			dfs(0, 0, 0);
			System.out.println("#" + t + " " + max);
		}
	}
}