[C++][백준 17208] 카우버거 알바생

문제

접근 방법

치즈버거, 감자튀김을 배열로 관리해 주는 방법으로 해결해 줄 수 있다.
개수에 따른 최대 주문의 개수를 기록해 주는 것이다.

최대 주문의 개수는 현재 값을 그대로 유지하거나 주문에서 요구하는 치즈버거, 감자튀김의 요구 개수를 감당할 수 곳에서의 최대 주문의 개수를 받아오는 것이다.

이 과정에서 3차원 또는 2차원으로 DP를 활용해서 해결해 줄 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, K, answer;
vector<vector<int>> dp;
vector<int> burgers, fries;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> K;

    dp = vector<vector<int>>(M + 1, vector<int>(K + 1));
    burgers = fries = vector<int>(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> burgers[i] >> fries[i];
    }

    for (int i = 0; i < N; ++i)
    {
        int burger = burgers[i];
        int fry = fries[i];

        for (int j = M; j >= burger; --j)
        {
            for (int k = K; k >= fry; --k)
            {
                int nextDP = dp[j - burger][k - fry] + 1; // 치즈버거, 감자튀김의 요구 개수를 감당할 수 있는 값
                if (nextDP > dp[j][k])                    // 새로운 값이 이전 값보다 크다면
                {
                    dp[j][k] = nextDP;
                    answer = max(answer, dp[j][k]);
                }
            }
        }
    }
    cout << answer;
    return 0;
}

풀이

3개의 반복문을 돌 것이다.
주문의 수, 치즈버거의 개수, 감자튀김의 개수로 말이다.

각 주문마다, 현재 치즈버거의 개수, 감자튀김의 개수마다 그대로 유지할지 아니면 현재 주문을 적용해 줄지를 판단할 수 있다.

하지만 반복문을 순서대로 돈다면 이전의 값이 다음의 값에 영향을 줄 것이다. 주문의 중복을 허용한다면 모르겠지만 그렇지 않다면 중복 적용되어서 값의 오류가 생긴다.

그렇기에 몇 번째 주문인지를 추가하여서 3차원 DP로 활용하는 것이다.
하지만 굳이 그럴 필요 없이 2차원 DP로도 해결이 가능하다.
바로 역방향으로 반복문을 도는 것이다.
그렇게 되면 겹치지 않기 때문에 문제가 발생하지 않는다.