SW expert 5215번 햄버거 다이어트 D3 - DFS

다이어트 하자 민기야

 

햄버거 재료를 제한된 칼로리에 맞게 조합하고, 민기의 선호도가 가장 높은 조합의 점수를 출력하면 된다.

DFS를 이용해 재귀를 통해 제한된 칼로리 이내의 모든 경우를 찾아 주었다.

 

import java.io.*;
import java.util.*;
 
class Solution { // swea 5215. 햄버거 다이어트 D3
    // 칼로리 범위 내에서 모든 재료 넣어서 최대값 구하기.
    public static boolean used[];
    public static int[][] ingredient;
    public static int answer, N, L;
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt(); // 재료 수
            L = sc.nextInt(); // 칼로리 제한
            answer = 0;
            used = new boolean[N];
            ingredient = new int[N][2];
            for (int i = 0; i < N; i++) {
                ingredient[i][0] = sc.nextInt(); // 맛 점수
                ingredient[i][1] = sc.nextInt(); // 칼로리
            }
            dfs(0, 0, 0);
            System.out.println("#" + tc + " " + answer);
        }
    }
 
    public static void dfs(int depth, int cal, int point) {
        answer = Math.max(answer, point);
        for (int i = depth; i < N; i++) {
            if (cal + ingredient[i][1] <= L && !used[i]) {
                used[i] = true;
                dfs(depth + 1, cal + ingredient[i][1], point+ingredient[i][0]);
                used[i] = false;
            }
        }
    }
}
 

 

아 간단하네~ 했는데

에?

T가 높은 인풋도 있나보다.

public static void dfs(int depth, int cal, int point) {
		answer = Math.max(answer, point);
		for (int i = depth; i < N; i++) {
			if (cal + ingredient[i][1] <= L && !used[i]) {
				used[i] = true;
				dfs(depth + 1, cal + ingredient[i][1], point+ingredient[i][0]);
				used[i] = false;
			}
		}
	}

 

dfs에서 가지를 칠게 있을까 싶었다.

근데 모르겠어. 왜 왜 오버야 왜이래 좀

 

그냥 단순히 더 줄여버렸다. 재료를 쓰거나 안쓰거나로..

둘다 n^2 라고 생각하는데... 흠

 

public static void dfs(int depth, int cal, int point) {
		if (cal > L) {
			return;
		}
		// 모든경우 다 찾았으므로
		if (depth == N) {
			answer = Math.max(answer, point);
			return;
		}
		
		dfs(depth + 1, cal + ingredient[depth][1], point + ingredient[depth][0]);
		dfs(depth + 1, cal, point);
	}

 

 

간결하네 간결해.

기존에는 조건에 부합하면 dfs를 돌려주었다. 넣었을때 칼로리가 초과되지 않는다면 dfs를 진행했다면

수정된 코드는 현재 번호의 재료를 쓰거나, 안쓰거나로 나눠 모든 경우를 탐색했다.

 

import java.io.*; import java.util.*; class Solution { // swea 5215. 햄버거 다이어트 D3 // 칼로리 범위 내에서 모든 재료 넣어서 최대값 구하기. public static int[][] ingredient; public static int answer, N, L; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); // 재료 수 L = sc.nextInt(); // 칼로리 제한 answer = 0; ingredient = new int[N + 1][2]; for (int i = 0; i < N; i++) { ingredient[i][0] = sc.nextInt(); // 맛 점수 ingredient[i][1] = sc.nextInt(); // 칼로리 } dfs(0, 0, 0); System.out.println("#" + tc + " " + answer); } } public static void dfs(int depth, int cal, int point) { if (cal > L) { return; } // 모든경우 다 찾았으므로 if (depth == N) { answer = Math.max(answer, point); return; } dfs(depth + 1, cal + ingredient[depth][1], point + ingredient[depth][0]); dfs(depth + 1, cal, point); } }