C++로 풀어보는 '요리 줄이기' 문제: 최대 만족도 계수 구하기

문제 개요

한 명의 셰프가 있다고 가정해 봅시다. 셰프는 자신이 만들 수 있는 n개의 요리에 대한 만족도(satisfaction) 데이터를 미리 수집해 두었습니다. 셰프는 어떤 요리든 1단위 시간 안에 완성할 수 있습니다.

각 요리의 좋아요 시간 계수(Like-time coefficient)는 해당 요리까지 포함한 누적 조리 시간에 그 요리의 만족도를 곱한 값으로 정의됩니다. 즉, time[i] * satisfaction[i] 입니다.

우리의 목표는 요리 준비 과정에서 얻을 수 있는 좋아요 시간 계수의 합 중 최댓값을 찾는 것입니다. 요리는 어떤 순서로든 조리할 수 있으며, 최댓값을 얻기 위해 일부 요리를 아예 만들지 않고 버리는 것도 허용됩니다.

예를 들어 입력이 [-1, -7, 0, 6, -7]이라면 출력은 17입니다. 두 번째 요리(-7)와 마지막 요리(-7)를 제거하면, 최대 좋아요 시간 계수의 합은 -1*1 + 0*2 + 6*3 = 17이 됩니다.

접근 방법

이 문제는 동적 계획법(DP)과 메모이제이션을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 배열을 오름차순으로 정렬한 뒤, 각 요리에 대해 '만든다' 또는 '건너뛴다' 두 가지 선택지를 재귀적으로 탐색하는 것입니다. 단계별로 살펴보겠습니다.

크기가 505 × 505인 DP 배열 dp를 선언합니다.
solve() 함수를 정의합니다. 이 함수는 현재 인덱스 idx, 현재 시간 time, 배열 v를 인자로 받습니다.
idx가 배열 v의 크기와 같다면 모든 요리를 검토했다는 의미이므로 0을 반환합니다.
dp[idx][time] 값이 -1이 아니라면 이미 계산된 결과이므로 그 값을 그대로 반환합니다(메모이제이션).
ret을 음의 무한대(INT_MIN)로 초기화합니다.
ret을 다음 두 값 중 더 큰 값으로 갱신합니다:
- 현재 요리를 건너뛰는 경우: solve(idx + 1, time, v)
- 현재 요리를 만드는 경우: v[idx] * time + solve(idx + 1, time + 1, v)
dp[idx][time]에 ret을 저장하고 이를 반환합니다.
메인 함수에서는 다음 작업을 수행합니다:
- memset을 사용해 dp 배열 전체를 -1로 초기화합니다.
- 배열 v를 오름차순으로 정렬합니다. 이렇게 하면 만족도가 낮은(특히 음수인) 요리는 자연스럽게 앞쪽에 배치되어 건너뛰기 쉬워지고, 만족도가 높은 요리는 나중에 조리되어 더 큰 시간 배율을 곱받게 됩니다.
- solve(0, 1, v)를 호출하여 최종 결과를 반환합니다.

시간 복잡도는 상태의 수(idx × time)가 최대 O(n²)이고 각 상태의 전이가 O(1)이므로 전체 O(n²)이며, 공간 복잡도 역시 DP 테이블 크기만큼 O(n²)입니다.

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int dp[505][505];
    int solve(int idx, int time, vector <int>& v){
       if(idx == v.size()) return 0;
       if(dp[idx][time] != -1) return dp[idx][time];
       int ret = INT_MIN;
       ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx
       + 1, time + 1, v));
       return dp[idx][time] = ret;
    }
    int maxSatisfaction(vector<int>& v) {
       memset(dp, -1, sizeof(dp));
       sort(v.begin(), v.end());
       return solve(0, 1, v);
    }
};
main(){
    Solution ob;
    vector<int> v = {-1,-7,0,6,-7};
    cout << (ob.maxSatisfaction(v));
}

입력

{-1,-7,0,6,-7}