📝 문제 정보#
🧐 관찰 및 접근#
- 수열을 원하는 개수의 연속된 구간으로 나누어서
- 구간의 합이 양수인 개수 - 구간의 합이 음수인 개수를 양수로 만들자.
- 직관적으로 생각해보자.
- 지금까지의 합이 양수면 -> 걍 잘라버리는게 이득이다.
- 지금까지의 합이 음수면 -> 이게 좀 고민이네
- 다음 놈이 음수면 -> 계속 먹으면 되는데, -100 -100 -100 1 -100 같은 경우에는 한번에 큰덩이로 먹는게 이득일수도 있지 않나?
- 일단 양수/음수는 묶어서 생각할 수 있을거같고, 음수 친구를 왼쪽/오른쪽으로 보내서 양수 덩어리에 합류시킬지 말지만 고민하면 되는것같다.
- 그렇다면 양수 / 양수 / 음수 / 양수 / 음수 / 양수 이렇게 생겼을텐데, 이제는 음수인 것이 두개 이상 붙어서 등장하지 않는다.
- 양수 개수 > 음수 개수라면 1을 출력하면 된다!
- 양수 개수 = 음수 개수라면 한 칸이 결합 가능한지 생각하면 된다!
- 양수 개수 < 음수 개수라면 두 칸이 결합 가능한지 생각하면 된다!
- 이게 두번 확인해야해서 문제지만, 결합 가능하면 무조건 결합한다는 방식이 그리디하게 가능하다. 직관적이긴 하네
- 라고!!!!!!!! 생각했지만!!!!!!!!! 틀렸다.
- $[2, -1, -1, 2, -1, -1]$ 의 경우.. $(2, -1), (-1, 2), (-1, -1)$로 묶으면 된다. 그러니까 맘대로 묶으면 안된다는건데….
- 그리디 문제 추천받아서 풀던거라 여기서 DP로 틀진 않았고, 솔직히 평소같았으면 세그DP로 튀었을듯
- $[2, -1, -1, 2, -1, -1]$ 의 경우.. $(2, -1), (-1, 2), (-1, -1)$로 묶으면 된다. 그러니까 맘대로 묶으면 안된다는건데….
💻 풀이#
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<ll> v;
ll sum = 0;
rep(i, 0, N){
ll x; cin >> x;
if(x != 0) v.push_back(x);
sum += x;
}
if(v.size() == 0){
cout << "NO\n";
return;
}
ll cur = 0;
int pcnt = 0, ncnt = 0;
for(auto x: v){
if(x > 0){
if(cur <= 0 && cur +x > 0) cur += x;
else{
if(cur > 0) pcnt++;
if(cur < 0) ncnt++;
cur = x;
}
}
else{
if(cur > 0 && cur + x <= 0){
if(cur > 0) pcnt++;
if(cur < 0) ncnt++;
cur = x;
}
else{
cur += x;
}
}
// cout << "cur: " << cur << " pcnt: " << pcnt << " ncnt: " << ncnt << "\n";
}
if(cur > 0) pcnt++;
if(cur < 0) ncnt++;
cout << (pcnt > ncnt ? "YES" : "NO") << "\n";
}