[SWEA] 5215. 햄버거 다이어트 (D3) / C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=5215&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

 

DFS 완전 탐색

음.. DFS로 완전탐색하여 맛 점수 합의 최대값을 구하려고 했다.

처음 작성한 코드에서 시간 초과로 통과가 되지 않음

↓아래가 해당 코드이다↓

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int result = 0;
int N, L;
vector<pair<int, int>> ingredients;
 
void Hamburger(int calories, int score, vector<bool> visit)
{
    vector<int> candidate;
 
    for (int i = N - 1; i >= 0; i--)
    {
        // 더 이상 방문할 수 없으므로, score 출력
        if (visit[i] == false)
        {
            if ((calories - ingredients[i].second) < 0)
            {
                if (result < score)
                {
                    //cout << score << "로 점수 갱신" << "\n";
                    result = score;
                }
            }
            else
                candidate.push_back(i);
        }
    }
 
    if (candidate.size() == 0)
            return;
 
    for (int index : candidate)
    {
        vector<bool> setVisit = visit;
        setVisit[index] = true;
        Hamburger(calories - ingredients[index].second, score + ingredients[index].first, setVisit);
    }
 
}
 
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
 
    //freopen("input.txt", "r", stdin);
    cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> L;
        vector<bool> visited;
        for (int i = 0; i < N; i++)
        {
            int score, calories;
            cin >> score >> calories;
            ingredients.push_back({ score, calories });
            visited.push_back(false);
        }
        sort(ingredients.begin(), ingredients.end());
 
        Hamburger(L, 0, visited);
 
        cout << "#" << test_case << " " << result << "\n";
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

뭐가 잘못된건지 다시봐도 모르겠어서, 다른 분들의 코드를 참고했다 ...

vector<pair<int, int>> ingredients; //재료의 맛점수와 칼로리
vector<int> calories;
vector<int> scores;
int N, L;
int maxFoodScore = -1;
bool visited[21];
 
int caloriesSum()
{
    int sum = 0;
    for (int i = 0; i < calories.size(); i++)
        sum += calories[i];
 
    return sum;
}
 
int scoresSum()
{
    int sum = 0;
    for (int i = 0; i < scores.size(); i++)
        sum += scores[i];
 
    return sum;
}
 
void dfs(int n)
{
    //현재까지 칼로리의 합이 제한 칼로리보다 높다면 종료
    if (caloriesSum() > L) return;
 
    //현재까지 칼로리의 합이 제한 칼로리보다 작다면, 우선 맛점수 최대값 Set
    if (maxFoodScore < scoresSum())
        maxFoodScore = scoresSum();
 
    for (int i = n; i < ingredients.size(); i++)
    {
        // 아직 방문하지 않은 경우 진입
        if (!visited[i])
        {
            visited[true];
            scores.push_back(ingredients[i].first);
            calories.push_back(ingredients[i].second);
 
            dfs(i + 1);
 
            visited[i] = false;
            scores.pop_back();
            calories.pop_back();
        }
    }
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
 
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
 
        cin >> N >> L; //N:재료의 수, L:제한 칼로리
        for (int i = 0; i < N; i++)
        {
            int score, calories;
            cin >> score >> calories;
            ingredients.push_back({ score, calories });
        }
 
        dfs(0);
 
        cout << "#" << test_case << " " << maxFoodScore << "\n";
 
        ingredients.clear();
        scores.clear();
        ingredients.clear();
        maxFoodScore = -1;
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

내가 DFS를 좀 꼬아서 사용한 것 같긴하다..

 

 

 

 

또한 해당 문제는 0-1 knapsack 알고리즘으로 풀 수 있다고 하는데, 해당 개념을 다루고 넘어가자!

0-1 knapsack

먼저 Knapsack Problem이란, Dynamic Programming을 사용하는 기본적인 문제이다.

도둑이 보석가게에 배낭을 메고 침입했다.
배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다.
각 보석들의 무게와 가격은 알고 있다.
배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?

 

따라서 $W$를 넘지않으면서 이득을 최대화하기 위해

각 보석을 넣을 것인지(1), 말 것인지(0) 결정하는 것!

 

 

DP는 전체의 큰 문제를 작은 문제로 쪼개어서 풀 수 있는지 확인하면 된다고 한다.

위 문제를 한 번 쪼개보자

 

• $w$는 배낭에 들어간 무게 (0<$w$<$W$)
• P[i][w]: $i$번째의 item까지 고려하였고, 무게의 한도가 $w$일 때 최적의 이익

1) 보석을 더 넣을 수 있긴 한 경우
1-1) 보석을 넣은 경우: P[$i-1$][$w - w_i$] + $p_i$
1-2) 보석을 넣지 않음: P[$i-1$][$w$]

2) 보석을 더 이상 넣을 수 없음($w_i$ > $w$) : P[$i-1$][$w$]

 

1)번 경우에서 최적의 방법을 판단하는 법은? 이득이 최대가 되는 것

 

따라서 P[i][w]의 점화식을 작성해보면 아래와 같다.

if (wi <= w):
    max( P[i-1][w-wi] + pi , P[i-1][w])
 
else
    P[i-1][w]

 

 

c++로 5215번을 풀어보자!

int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++)
    {
        // l = 제한 칼로리
        cin >> n >> l;
 
        int score[21];
        int cal[21];
 
        for (int i = 1; i <= n; i++)
        {
            cin >> score[i] >> cal[i];
        }
 
        for (int i = 1; i <= n; i++)
        {
            // 1 칼로리부터 최대 칼로리까지 확인함
            for (int j = 1; j <= l; j++)
            {
                if (cal[i] > j) 
                    // 이번 순서의 재료 칼로리가 더 크다면, 못 넣음(이전 순서의 이득과 동일함)
                    dp[i][j] = dp[i - 1][j];
                else
                    // 이번 순서의 재료 칼로리가 더 낮음. 새로 넣을 수 있는데
                    // 1) 이전 순서의 이득 과 
                    // 2) 이전 순서 시점에서, 이번 재료 칼로리만큼 빠졌을 때 가질 수 있었던 점수 이득을 판단한다
                    // 1)이 더 우세하면 안 넣고 넘어가는 것이고, 아니라면 넣고 넘어간다.
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cal[i]] + score[i]);
 
                cout << i << " " << j << "\n";
            }
        }
        cout << "#" << t + 1 << " " << dp[n][l] << '\n';
    }
 
    return 0;
}

 

DP table이 어떻게 채워지는지 궁금해서 출력해보았음.. 궁금하면 펼치시오

1 1
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 2
0 0 0 0 0 0 0 0 0 0 0
0 0 100 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 3
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 4
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 5
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 6
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 7
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 8
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 9
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
1 10
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 1
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 2
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 3
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 4
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 5
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 6
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 7
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 8
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 9
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
2 10
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 1
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 2
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 3
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 4
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 5
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 6
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 7
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 8
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 9
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
3 10
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 1
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 2
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 3
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 4
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 5
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 6
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 7
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 0 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 8
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 0 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 9
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 0
0 0 0 0 0 0 0 0 0 0 0
-------
4 10
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 0 0 0 0 0 0 0 0 0
-------
5 1
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 0 0 0 0 0 0 0 0 0
-------
5 2
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 0 0 0 0 0 0 0 0
-------
5 3
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 0 0 0 0 0 0 0
-------
5 4
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 0 0 0 0 0 0
-------
5 5
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 0 0 0 0 0
-------
5 6
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 500 0 0 0 0
-------
5 7
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 500 650 0 0 0
-------
5 8
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 500 650 650 0 0
-------
5 9
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 500 650 650 750 0
-------
5 10
0 0 0 0 0 0 0 0 0 0 0
0 0 100 100 100 100 100 100 100 100 100
0 0 100 100 100 300 300 400 400 400 400
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 250 350 350 400 550 550 650
0 0 100 250 400 400 500 650 650 750 750
-------