[SWEA] #5215 _ 햄버거 다이어트

[햄버거 다이어트] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

dfs를 이용하여 모든 경우의 수를 모두 해보고 가장 높은 점수를 출력하면 된다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>

using namespace std;
int N, L, max_score;
int ingredient[21][21] = { 0, };

int solve(int idx, int kcal, int score);
int main() {
	int test_case;

	scanf("%d", &test_case);
	for (int i = 1; i <= test_case; i++) {
		max_score = 0;
		scanf("%d %d", &N, &L);
		for (int j = 0; j < N; j++) scanf("%d %d", &ingredient[j][0], &ingredient[j][1]); // Input kcal, score
		for (int j = 0; j < N; j++) solve(j, 0, 0);
		printf("#%d %d\n", i, max_score); // Print result
	}

	return 0;
}

int solve(int idx, int kcal, int score) {
	if (kcal > L) return 0;
	max_score = max(max_score, score);

	for (int i = idx + 1; i <= N; i++) solve(i, kcal + ingredient[idx][1], score + ingredient[idx][0]);
}