Algorithm/SWEA
5215. 햄버거 다이어트
benguin
2019. 8. 2. 16:31
[URL]
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
[풀이 과정]
* 재귀DFS 2진탐색 (깊이 N까지)
[소스 코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <stdio.h>
int N;
int L;
int food[21];
int cal[21];
bool flag[21] = { 0, };
bool check[21] = {0, };
int totalCnt;
int max;
void go(int cnt) {
if (cnt == N)
{
// 계산 띠
int tempFood = 0;
int tempLimit = 0;
for (int i = 0; i < N; i++)
{
tempFood += (flag[i] * food[i]);
tempLimit += (flag[i] * cal[i]);
}
if (tempLimit <= L)
{
if (max <= tempFood)
{
max = tempFood;
}
}
return;
}
for (int i = 0; i < 2; i++)
{
if (check[cnt] == false)
{
check[cnt] = true;
flag[cnt] = i;
go(cnt + 1);
check[cnt] = false;
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int tc = 0; tc < T; tc++)
{
totalCnt = 0;
max = -1;
scanf("%d", &N);
scanf("%d", &L);
for (int i = 0; i < N; i++)
{
int inputFood, inputCal;
scanf("%d %d", &inputFood, &inputCal);
food[i] = inputFood;
cal[i] = inputCal;
}
go(0);
printf("#%d %d\n", tc+1, max);
}
return 0;
}
|
cs |