Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 다이나믹 프로그래밍으로 해결하는 작업 일정 최소 난이도 문제

문제 개요

주어진 작업 목록을 d일에 걸쳐 수행하는 일정표를 만드는 문제입니다. 작업들 사이에는 의존 관계가 있어서, i번째 작업을 처리하려면 그 앞에 있는 모든 작업(0 ≤ j < i)을 먼저 완료해야 합니다.


또한 매일 최소 한 개 이상의 작업을 반드시 완료해야 하며, 일정 전체의 난이도는 d일 각각의 난이도를 모두 더한 값으로 정의됩니다. 이때 하루의 난이도란 그날 수행한 작업 중 가장 높은 난이도를 의미합니다.


정수 배열 jobDifficulty와 정수 d가 입력으로 주어지며, i번째 작업의 난이도는 jobDifficulty[i]입니다. 우리가 구해야 할 것은 전체 일정의 최소 난이도이고, 만약 유효한 일정을 만들 수 없다면 -1을 반환해야 합니다.

입력 예시와 결과

jobDifficulty = [6,5,4,3,2,1], d = 2인 경우를 살펴보겠습니다.

C++ 다이나믹 프로그래밍으로 해결하는 작업 일정 최소 난이도 문제

첫째 날에는 처음 5개의 작업(난이도 6, 5, 4, 3, 2)을 모두 처리합니다. 이때 첫째 날의 난이도는 최댓값인 6입니다. 둘째 날에는 마지막 작업(난이도 1)을 처리하므로 둘째 날의 난이도는 1이 됩니다. 따라서 전체 일정의 난이도는 6 + 1 = 7이며, 이것이 만들 수 있는 최소 난이도입니다.

풀이 접근 방식

이 문제는 메모이제이션(memoization)을 활용한 재귀적 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 'idx번째 작업부터 시작하여 남은 k일 동안 나머지 작업을 모두 마칠 때의 최소 난이도'를 상태로 정의하는 것입니다.

단순히 매일 최대한 많은 작업을 몰아서 처리하는 탐욕적(greedy) 방법은 항상 최적해를 보장하지 못합니다. 따라서 각 날짜에 어느 작업까지 포함할지를 가능한 모든 경우에 대해 시도하면서 최솟값을 찾아야 하며, 중복 계산을 피하기 위해 dp 배열에 계산 결과를 저장해 두었다가 재사용합니다.

알고리즘 단계

배열 v, 현재 인덱스 idx, 남은 일수 k, 2차원 dp 배열을 매개변수로 받는 solve() 함수를 다음과 같이 정의합니다.

  1. idx가 배열의 크기와 같고 k가 0이면, 모든 작업을 d일에 성공적으로 배분한 것이므로 0을 반환합니다.
  2. k가 음수이거나, idx가 배열의 끝에 도달했는데 k가 여전히 0보다 크면 유효하지 않은 상태이므로 큰 값(10^6)을 반환합니다.
  3. dp[idx][k]가 -1이 아니라면 이미 계산된 결과이므로 그 값을 그대로 반환합니다.
  4. maxVal을 0으로, ret을 INT_MAX(무한대)로 초기화합니다.
  5. i를 idx부터 배열 끝까지 증가시키며 반복합니다.
    - maxVal을 v[i]와 비교하여 더 큰 값으로 갱신합니다.
    - ret을 'maxVal + solve(v, i + 1, k - 1, dp)'와 비교하여 더 작은 값으로 갱신합니다.
  6. dp[idx][k]에 ret을 저장한 뒤 ret을 반환합니다.

메인 함수(minDifficulty)에서는 다음 순서로 진행합니다.

  1. n을 작업 배열의 크기로 설정합니다.
  2. d > n이면 매일 최소 한 개의 작업을 해야 한다는 조건을 만족할 수 없으므로 -1을 반환합니다.
  3. n × (d + 1) 크기의 2차원 dp 배열을 선언하고 모든 값을 -1로 초기화합니다.
  4. solve(j, 0, d, dp)의 결과를 반환합니다.

복잡도 분석: 시간 복잡도는 O(n² × d), 공간 복잡도는 O(n × d)입니다. 여기서 n은 작업의 개수, d는 일수입니다.

C++ 구현 코드

아래 예제를 통해 실제 구현 내용을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& v, int idx, int k, vector<vector<int> >&
   dp){
      if (idx == v.size() && k == 0)
      return 0;
      if (k < 0 || idx == v.size() && k > 0)
      return 1e6;
      if (dp[idx][k] != -1)
      return dp[idx][k];
      int maxVal = 0;
      int ret = INT_MAX;
      for (int i = idx; i < v.size(); i++) {
         maxVal = max(v[i], maxVal);
         ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp));
      }
      return dp[idx][k] = ret;
   }
   int minDifficulty(vector<int>& j, int d){
      int n = j.size();
      if (d > n)
      return -1;
      vector<vector<int> > dp(n, vector<int>(d + 1, -1));
      return solve(j, 0, d, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {6,5,4,3,2,1};
   cout << (ob.minDifficulty(v, 2));
}

실행 결과

입력

{6,5,4,3,2,1}, 2

출력

7