문제 개요
숫자 목록 jobs와 정수 k가 주어졌다고 가정해 보겠습니다. 우리는 모든 작업을 정확히 k일에 걸쳐 완료해야 합니다. 작업은 반드시 주어진 순서대로 수행해야 하며, 각 날에는 하나 이상의 연속된 작업을 처리해야 합니다.
i번째 작업의 난이도는 jobs[i]에 저장되어 있고, 특정 하루의 난이도는 그날 수행한 작업 중 가장 높은 난이도로 정의됩니다. 따라서 우리가 구해야 하는 것은 k일에 걸쳐 모든 작업을 수행할 때의 난이도 총합의 최솟값입니다.
입력 예시
예를 들어 입력이 jobs = [2, 3, 4, 6, 3], k = 2라면 출력은 8이 됩니다.
- 첫째 날: [2]를 수행 → 난이도 2
- 둘째 날: [3, 4, 6, 3]을 수행 → 난이도 max(3, 4, 6, 3) = 6
따라서 전체 난이도 합계는 2 + 6 = 8이 됩니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)과 메모이제이션을 활용하면 효율적으로 해결할 수 있습니다. 재귀 함수 dfs()를 통해 "start번째 작업부터 시작하여 남은 k일로 작업을 마칠 때의 최소 난이도 합계"를 구하고, 이미 계산한 결과는 dp 테이블에 저장해 두었다가 재사용함으로써 불필요한 중복 계산을 제거합니다.
구체적인 풀이 단계는 다음과 같습니다.
- 크기가 505 × 15인 2차원 배열 dp를 선언합니다.
start,k, 배열v를 매개변수로 받는 함수dfs()를 정의합니다.- 만약 start가 v의 크기보다 크거나 같다면, k가 0일 때는 0을, 그렇지 않으면 무한대(inf)를 반환합니다. (모든 작업을 마쳤는데 일수가 남아 있거나 부족한 경우)
- 만약 k < 0이라면 무한대(inf)를 반환합니다. (정해진 일수를 초과해 사용한 경우)
- 만약 dp[start][k]가 -1이 아니라면, 이미 계산된 값이므로 dp[start][k]를 그대로 반환합니다.
- ret을 무한대(inf)로, val을 0으로 초기화합니다.
- i를 start부터 v의 끝까지 1씩 증가시키며 다음을 반복합니다.
- val을 val과 v[i] 중 더 큰 값으로 갱신합니다. (현재 날의 최대 난이도)
- ret을 ret과 (val + dfs(i + 1, k - 1, v)) 중 더 작은 값으로 갱신합니다.
- dp[start][k]에 ret을 저장한 뒤 ret을 반환합니다.
- 메인 함수에서는 dp 배열을 -1로 초기화한 후 dfs(0, k, jobs)를 호출해 결과를 얻습니다.
C++ 구현 예시
더 나은 이해를 돕기 위해 다음 구현 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];
int dfs(int start, int k, vector<int>& v){
if(start >= v.size()){
return k == 0 ? 0 : inf;
}
if(k < 0)
return inf;
if(dp[start][k] != -1)
return dp[start][k];
int ret = inf;
int val = 0;
for(int i = start; i < v.size(); i++){
val = max(val, v[i]);
ret = min(ret, val + dfs(i + 1, k - 1, v));
}
return dp[start][k] = ret;
}
int solve(vector<int>& jobs, int k) {
memset(dp, -1, sizeof dp);
return dfs(0, k, jobs);
}
int main(){
vector<int> v = {2, 3, 4, 6, 3};
int k = 2;
cout << solve(v, k);
}
입력
{2, 3, 4, 6, 3}, 2
출력
8
복잡도 분석
dfs 함수의 상태는 (start, k) 조합으로 최대 n × k개이며, 각 상태에서 최대 n번의 반복을 수행하므로 시간 복잡도는 O(n² × k)입니다. 공간 복잡도는 dp 테이블과 재귀 호출 스택을 포함하여 O(n × k)입니다.