https://www.acmicpc.net/problem/28433
난이도가 좀 있는 그리디 알고리즘 문제. 그리디 문제답게 풀이를 떠올리고 증명하는 것에 약간 시간이 걸렸다.
나의 풀이 흐름은 다음과 같았다.
처음에는 dp[i]=max(dp[j]+(sum(i+1 ~ j)?1:-1))과 유사한 형태의 점화식을 가진 dp문제가 아닐까 의심을 해보았는데 이 경우 O(N^2) 정도의 시간복잡도가 나올 것으로 보여 N<=200000인 이 문제에서는 부적절하다고 판단, 그리디로 방향을 전환했다.
쉬운 이해를 위해 연속 음수 구간이라는 용어를 정의하겠다. 아래의 설명에서 연속 음수 구간은 수열의 i번째 항에서 j번째 항까지가 전부 음수이고(i<=j), i-1번이나 j+1은 양수인 구간을 뜻한다.
예를들어 {-5, 4, 2, -3, -1, 7}에서 연속 음수 구간은 {-5}, {-3, -1}이다.
다시 문제로 돌아와 문제를 잘 관찰해보니 수열에서 하나의 연속 음수인 구간에서 그 일부만을 근처에 있는 양수와 합쳐 제거하는 것은 불필요한 행동이라는 것을 발견했다. (해당 연속 음수 구간 전체를 제거할게 아니라면 그냥 그 구간을 하나로 합쳐버리는 것만으로 최적이 되기 때문)
따라서 하나의 연속 음수 구간을 구간의 왼쪽이나 오른쪽에 있는 양수인 항 단 하나와 합쳤을 때 0보다 커야만 합치는 것에 의미가 있다고 판단했다. (만약 두 개의 양수 항과 합쳐 연속 음수 구간을 상쇄시킨다면 양수 항이 하나가 줄고 음수항이 하나가 줄게 되므로 불필요한 행동이 된다)
그래서 처음에는 수열에서 연속 음수 구간들은 각각 하나로 미리 합쳐둔 뒤, 왼쪽에 있는 연속 음수 구간부터 구간의 왼쪽 양수 항이 연속 음수 구간의 합보다 절대값이 크면 합치고 그렇지 않으면 오른쪽의 양수 항과 비교하여 절대값이 크면 합치는 방식으로 구현을 하여 제출했다. (현재 체크하고 있는 연속 음수 구간보다 뒤에 있는 연속 음수 구간들은 현재 연속 음수 구간의 오른쪽에 있는 양수 항만 사용이 가능할 것이기 때문에 왼쪽에 있는 양수 항을 우선적으로 사용)
하지만 막상 제출을 해보니 WA를 받았다.
잘 생각해보니 놓친 부분이 있었는데 연속 음수 구간을 꼭 구간의 왼쪽과 오른쪽 중 한쪽의 양수 항에서 커버할 필요가 없고 일부는 왼쪽, 일부는 오른쪽에서 커버하는 방법이 가능했다.
따라서 연속 음수 구간의 왼쪽 부분부터 왼쪽 양수 항이 가능한 만큼(즉, 합쳐도 0보다 클때까지) 커버하도록 하고 그 이후는 계속해서 오른쪽 항으로 값을 넘겨주다가 그 다음 항이 양수항일때 만약 쌓여있는 값을 오른쪽 양수 항이 커버가 가능하다면(즉, 합쳐도 0보다 크다면) 합쳐주고 그렇지 않다면 합치지 않는 방식으로 구현을 하고 제출을 했더니 AC를 받았다.
참고로 값이 꽤 커질 수 있으므로 long long 자료형을 사용해야된다.
AC code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll T;
cin>>T;
while(T--) {
ll N,n1=0,n2=0,idx=-1;
cin>>N;
vector<ll> v(N);
for(ll i=0;i<N;i++) cin>>v[i];
for(ll i=0;i<N;i++) {
if(v[i]>0) idx=i;
else {
if(idx!=-1&&v[i]+v[idx]>0) {
v[idx]+=v[i];
v[i]=0;
}
else if(i<N-1) {
idx=-1;
if(v[i+1]<=0||v[i+1]+v[i]>0) {
v[i+1]+=v[i];
v[i]=0;
}
}
}
}
for(auto i:v) {
if(i>0) n1++;
else if(i<0) n2++;
}
if(n1>n2) cout<<"YES\n";
else cout<<"NO\n";
}
}
그리디 문제, 특히 고난이도의 그리디 문제는 특별한 알고리즘을 쓰는게 아니다 보니 원래 알고리즘으로 인해서 올라갈 난이도만큼 머리를 더 쓰게되는 거 같다. 그래서 비슷한 난이도의 다른 문제들에 비해서 더 어렵게 느껴지지만 한편으로는 풀었을 때의 상쾌함도 더 크게 느껴진다.
댓글남기기