백준 28433 - 게리맨더링 (C++)

문제

• 문제 링크

  
   BOJ 28433 - 게리맨더링 
  

• 문제 요약

길이 $N$의 수열이 주어질 때, 이 수열을 원하는 개수의 연속된 구간으로 나누어 각 구간의 합을 계산한다.
이때, 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과하도록 할 수 있을까$?$

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 2*10^5$

$-10^9 ≤ N_i ≤ 10^9$

$1 ≤ T ≤ 10^4$

입력에서 주어지는 $N$의 합은 $2*10^5$를 넘지 않는다.

알고리즘 분류

• 그리디 알고리즘(greedy)

풀이

다음의 일반적인 두 사항은 관찰을 통해 쉽게 알아낼 수 있다.

연속된 음수는 반드시 하나로 합치는 것이 최선이다.

연속된 양수는 반드시 별개로 보는 것이 최선이다.

이를 바탕으로 풀이를 고민해보자.
부분 연속 수열로 쪼개는 것이므로, 수를 읽어가며 현재 수를 이전 수열에 포함 할지 / 하지 않을지를 판단하자.

네 변수 $[sum, c1, c2, i]$는 각각 $[$이전 수열의 누적값, 음수 구간의 개수, 양수 구간의 개수, 현재 수$]$가 되겠다.

---

$i < 0$

앞서 말했듯이, $sum ≤ 0$ 이라면 현재 수를 반드시 이전 수열에 포함 시켜야 한다.

반대로 $sum > 0$ 이라면 아래와같이 두가지의 상황이 발생할 수 있다.

$sum + i > 0$ : 양수 수열을 유지할 수 있으므로, 현재 수를 이전 수열에 포함 시켜 음수를 최대한 없앤다.

$sum + i ≤ 0$ : 그나마 있던 양수 수열을 없앨 순 없으므로, $i$로부터 새로운 수열을 시작한다.

$i > 0$

앞서 말했듯이, $sum ≥ 0$ 이라면 현재 수로부터 반드시 새로운 수열을 시작해야 한다.

반대로 $sum < 0$ 이라면 아래와같이 두가지의 상황이 발생할 수 있다.

$sum + i > 0$ : 음수 수열인 이전 수열을 양수 수열로 바꿀 수 있는 귀중한 순간이므로, $i$를 이전 수열에 포함 시킨다.

$sum + i ≤ 0$ : 이전 수열에 $i$를 포함한들 양수 수열이 될 수 없으므로, 이전 수열을 하나의 음수 수열로 인정하고 $i$부터 새로운 수열을 시작한다.

이처럼 $i > 0$ 일 때 발생할 수 있는 $3$가지 상황에서의 공통점은 $c2$가 반드시 증가한다는 것이다.

$i == 0$

아무런 영향이 없다.

---

마지막으로 구현에 따라 다음의 예외 처리가 필요 할수도 / 필요 하지 않을 수도 있는데, 내가 겪었던 예외 상황이다.

$i ≤ 0$ 이고, 마지막 요소이면서 이전 수열이 음수 수열이었던 경우 $?$

위 구현을 따라 그냥 진행해버리면 마지막 음수 수열이 카운트 되지 않으므로, 예외 처리가 필요했다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
 
        ll sum{}, c1{}, c2{};
        for (ll i; n--;)
        {
            cin >> i;
            if (!i && !n && sum < 0) c1++;
            if (i < 0)
            {
                if (sum <= 0) sum += i;
                else
                {
                    if (sum + i > 0) sum += i;
                    else sum = i;
                }
                if (!n && sum < 0) c1++;
            }
            if (i > 0)
            {
                if (sum >= 0) sum = i;
                else if (sum + i > 0) sum += i;
                else sum = i, c1++;
                c2++;
            }
        }
        cout << (c1 < c2 ? "YES" : "NO") << '\n';
    }
}

comment

끝