5215. 햄버거 다이어트

[URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE

SW Expert Academy

[풀이 과정]

* 재귀DFS 2진탐색 (깊이 N까지)

 

[소스 코드]

 

#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;
}