Swea_5215

SWEA 5215번

Link: 5215번: 햄버거 다이어트

---

문제 설명

완전탐색으로 최적의 조합을 구하는 문제.

문제 보자마자 ‘이건 DFS쓰면 풀리겠구나’ 하는 생각은 들었다.

이렇게 생각하고 풀었는데, DFS 구현에서 정말 많이 헤맸다.

DFS랑 BFS는 그래도 구현방법을 다 외우고 있었다고 생각했었는데 벌써 다 까먹은 모양이다.

예전에 코딩테스트 볼때도 확실하게 몰랐던거니 당연할수도.

어떻게든 고쳐서 해보다 안되서 답 찾아서 풀었다.

핵심은 DFS를 쓰긴 하는데 각각의 재료를 포함했을때와 포함하지 않았을때를 반드시 같이 돌려야 한다는것.

제약조건에 따라 포함하거나 포함안하거나 따지면서 DFS 두번 돌리면 바로 풀린다.

아직도 정말 갈길이 멀다고 생각했다.

DFS, BFS는 자신있다고 생각했는데… 심지어 DFS로 풀어야된다는걸 알면서도 틀려서 더 자괴감 오진다.

될때까지 하자.

---

정답 코드

//
// Created by Keith_Lee on 07/01/2019.
//

#include <iostream>
#include <vector>

using namespace std;

int T;
int N, L;
int maximum = 0;

vector<pair<int, int>> base;

void DFS(int start, int calory, int score){
    if(start == N){
        maximum = maximum > score ? maximum : score;
        return;
    }
    if(calory + base[start].second <= L){
        DFS(start+1, calory+base[start].second, score+base[start].first); // start번째 재료 추가
    }
    DFS(start+1, calory, score); // start번째 재료 거름
}

int main(){
    cin >> T;

    for(int test=1; test<=T; test++){
        cin >> N >> L;

        for(int i=0; i<N; i++){
            int calory;
            int score;

            cin >> score >> calory;

            base.push_back(make_pair(score, calory));
        }

        DFS(0, 0, 0);

        cout << '#' << test << ' ' << maximum << '\n';
        while(!base.empty()){
            base.pop_back();
        }
        maximum = 0;
    }
}

---