문제
참고
해당 문제는 주어진 N개의 장소 중에서 벌통, 꿀벌1, 꿀벌2를 적절히 배치하여 벌들이 딸 수 있는 가능한 최대의 꿀을 출력하는 문제이다.
가장 먼저 문제의 입력 범위를 통해 가능한 시간복잡도 알고리즘을 생각하면, 입력 가능한 N의 최대값은 10^5이므로, 딸 수 있는 꿀의 최대값을 구하기 위해서는 O(NlogN) 이하의 알고리즘으로 접근해야 한다.
위와 같은 과정을 통해 사실상 선형탐색을 통해 최대값을 탐색해야 한다고 생각했다.
하지만 벌통을 기준으로 배열의 인덱스 0부터 N-1까지 1번씩 순회를 하면서 각 경우마다 꿀벌1, 꿀벌2가 위치할 수 있는 모든 경우와 그에 대한 꿀의 양을 O(N) 내지는 O(NlogN)으로 계산할 방법이 생각나지 않았다.
부족함을 인정하고 다른 사람의 풀이를 참고하여 정리한 접근법은 다음과 같다.
1) 가장 먼저, 시간복잡도를 고려하면 브루트포스(완전탐색)은 힘들다.
따라서, 모든 경우를 고려/탐색하기 위해 하나로 일반화하여 접근을 하면 안된다.
2) 모든 경우를 고려할 수 있는 하나의 방법을 고안하지 말고, 벌통과 꿀벌1, 2가 위치할 수 있는 경우를 나누어서 고려/접근한다.
이때, 고려할 수 있는 경우는 다음과 같다.
(1) 벌통 - 꿀벌1 - 꿀벌2
(2) 꿀벌1 - 벌통 - 꿀벌2
(3) 꿀벌1 - 꿀벌2 - 벌통
(1)와 (3)의 경우는 벌통을 기준으로 생각했을때, 최대 꿀을 얻기 위해 최소한 한마리의 벌의 위치는 고정시킬 수 있다.
따라서 남은 한마리의 꿀벌을 기준으로 크기 N의 배열을 탐색하면서, 각 경우에 대한 획득 가능한 벌꿀의 양을 계산할 수 있다.
이때, 각 경우에 대한 획득 가능한 벌꿀 양을 계산하기 위해 정직하게 배열을 탐색하면 O(N^2)의 시간복잡도를 갖게 된다.
따라서 이를 방지하기 위해, 누적합 개념을 활용한다.
인덱스 0부터 i까지의 채취 가능한 벌꿀의 합을 sum[i] 이라고 정의하고, 꿀벌2의 위치를 n-1, 꿀벌1의 위치를 i라고 하면, (1)의 경우 꿀벌2가 채취한 벌꿀의 양은 다음과 같이 생각할 수 있다.
total1 = sum[n-1] - honey[n-1] - honey[i] = sum[n-2] - honey[i]
여기서 honey[i]는 벌꿀 채취가 불가능한 꿀벌1의 초기 위치, honey[n-1]은 꿀벌2의 초기 위치를 의미한다.
마찬가지 조건에서 꿀벌1이 채취한 벌꿀의 양을 생각하면 다음과 같다.
total2 = sum[i] - honey[i] = sum[i-1]
따라서 (1)의 경우에서 꿀벌1이 n-1에 위치하고, 꿀벌2의 위치를 i라고 생각하면,
매 i에 대해 최종적으로 획득 가능한 벌꿀의 양은 다음과 같다.
total = total1 + total2
= sum[n-1] - honey[n-1] - honey[i] + sum[i-1]
= sum[n-2] - honey[i] + sum[i-1]
위의 예시에서 가장 핵심적인 부분은 누적합 개념을 활용하여 남은 벌꿀 한마리의 위치가 변할 때마다 해당 경우에서 채취 가능한 벌꿀의 양을 수식적으로 정의할 수 있다는 점이다.
그리고 이를 통해 각 경우에 따른 벌꿀 최댓값을 O(NlogN)으로 탐색할 수 있다.
(채취 가능한 최대 벌꿀의 양은 O(N)으로 가능하지만 sort 함수의 시간복잡도에 의해 최종적으로는 O(NlogN)으로 탐색)
(3)의 경우도 마찬가지로 비슷하게 정의할 수 있고, (2)의 경우는 벌통이 꿀벌 사이에 위치한 경우, 각 꿀벌은 배열의 첫, 마지막 위치에 있는 것이 채취 가능한 벌꿀의 최대값을 위해서는 필수적이기 때문에, 벌통을 기준으로 하여 위의 예시와 비슷하게 벌통 위치에 따른 각 경우마다 벌꿀 채취 양을 정의할 수 있다.
위의 내용을 반영한 전체 코드는 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt", "rt", stdin);
int n, temp, res, max=-2147000000;
cin >> n;
vector<int> pos(n + 1);
vector<int> sum(n + 1);
for (int i = 1; i <= n; i++) {
cin >> temp;
pos[i] = temp;
sum[i] = sum[i - 1] + pos[i];
}
for (int i = 2; i < n; i++) {
res = (sum[n] - sum[1] - pos[i]) + (sum[n] - sum[i]);
if (res > max) {
max = res;
}
}
for (int i = 2; i < n; i++) {
res = (sum[i] - sum[1]) + (sum[n - 1] - sum[i - 1]);
if (res > max) {
max = res;
}
}
for (int i = 2; i < n; i++) {
res = (sum[n - 1] - pos[i]) + sum[i - 1];
if (res > max) {
max = res;
}
}
cout << max << "\n";
return 0;
}