크기가 제각각인 3n개의 조각으로 이루어진 피자가 있다고 가정해 봅시다. 저와 두 친구는 다음과 같은 규칙에 따라 번갈아 가며 피자 조각을 나눠 갖습니다.
- 제가 먼저 원하는 피자 조각을 하나 자유롭게 선택합니다.
- 친구 Amal은 제가 고른 조각을 기준으로 반시계 방향에 인접한 다음 조각을 가져갑니다.
- 친구 Bimal은 제가 고른 조각을 기준으로 시계 방향에 인접한 다음 조각을 가져갑니다.
- 피자 조각이 더 이상 남지 않을 때까지 이 과정을 반복합니다.
피자 조각의 크기는 시계 방향 순서대로 배치된 원형 배열 slices로 표현됩니다. 목표는 이 규칙 안에서 제가 얻을 수 있는 조각 크기 합의 최댓값을 구하는 것입니다.
문제 예시
입력이 [9,8,6,1,1,8]이라면 정답은 16입니다. 매 차례마다 크기가 8인 조각을 고르면 되기 때문입니다. 만약 처음에 크기 9인 조각을 선택해 버리면 양쪽 친구들이 크기 8짜리 조각들을 잇달아 가져가므로 결과적으로 손해를 보게 됩니다.
접근 방법: 동적 계획법(DP)
이 문제는 본질적으로 원형으로 배치된 배열에서 서로 인접하지 않도록 n/3개의 조각을 선택해 합을 최대화하는 문제와 같습니다. 제가 한 조각을 고르면 그 양옆 조각들은 친구들에게 넘어가기 때문입니다. 해결 절차는 다음과 같습니다.
1단계: solve() 함수 정의
solve() 함수는 배열 v와 선택할 조각 수 m을 인자로 받아, 해당 구간에서 얻을 수 있는 최대 합을 반환합니다.
- n := v의 크기
- (n + 1) × (m + 1) 크기의 2차원 배열 dp1과 dp2를 각각 선언합니다.
- i := 0부터 i < n까지 반복하고, 각 i에 대해 j := 0부터 j <= m까지 반복합니다.
- x := v[i]
- j < m인 경우 다음을 수행합니다.
- dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp1[i][j] + x)
- dp1[i + 1][j] = max(dp1[i + 1][j], dp2[i][j], dp1[i][j])
- dp1[n][m]과 dp2[n][m] 중 더 큰 값을 반환합니다.
여기서 dp1은 직전 조각을 선택하지 않은 상태, dp2는 직전 조각을 선택한 상태(따라서 현재 조각은 선택 불가)를 나타냅니다. 이를 통해 인접한 조각을 연속으로 고를 수 없다는 제약을 자연스럽게 처리할 수 있습니다.
2단계: maxSizeSlices() 함수
- n := slices의 크기
- ret := 0으로 초기화
- ret := max(solve(인덱스 1부터 끝까지의 배열, n/3), slices[0] + solve(인덱스 2부터 끝-1까지의 배열, n/3 - 1))
- ret을 반환합니다.
첫 번째 경우는 맨 앞 조각을 건너뛰고 나머지 구간에서 답을 구하는 것이고, 두 번째 경우는 맨 앞 조각을 선택한 뒤 마지막 조각을 제외한 구간에서 나머지를 고르는 것입니다. 이처럼 원형 배열의 경계를 두 가지 경우로 나누면 문제를 일반적인 선형 DP로 변환할 수 있습니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int> v, int m){
int n = v.size();
vector<vector<int> > dp1(n + 1, vector<int>(m + 1));
vector<vector<int> > dp2(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
int x = v[i];
if (j < m)
dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp1[i]
[j] + x);
dp1[i + 1][j] = max({ dp1[i + 1][j], dp2[i][j],
dp1[i][j] });
}
}
return max(dp1[n][m], dp2[n][m]);
}
int maxSizeSlices(vector<int>& slices) {
int n = slices.size();
int ret = 0;
ret = max(solve(vector<int>(slices.begin() + 1,
slices.end()), n / 3), slices[0] + solve(vector<int>(slices.begin() +
2, slices.end() - 1), n / 3 - 1));
return ret;
}
};
main(){
Solution ob;
vector<int> v = {9,8,6,1,1,8};
cout << (ob.maxSizeSlices(v));
}
실행 결과 확인
입력
{9,8,6,1,1,8}
출력
16
시간 복잡도
solve() 함수는 i와 j에 대한 이중 반복문을 사용하므로 한 번 호출당 O(n × n/3)의 비용이 들고, 두 번 호출되므로 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도 역시 DP 테이블 크기에 비례하여 O(n²)입니다.