게리멘더링( BOJ 28433 )

문제 : https://www.acmicpc.net/problem/28433

28433번: 게리맨더링

 

문제 파악하기

합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요?

 

문제 해결하기

문제를 관찰해보면 음수를 최대한 없애야 한다는 걸 발견할 수 있습니다. 그렇다면 음수를 어떻게 하면 최대한 없앨 수 있을까요? 여기서부터는 상황에 따라 달라집니다. 정확한 상황 정의를 위해 현재 확인할 숫자(inp[i])와 이전까지 구분했던 구간의 합(cur)을 중심으로 비교해보겠습니다.

 

1. inp[i] > 0인 경우 

현재 숫자가 양수인 경우에는 나올 수 있는 경우의 수가 총 3가지 있습니다.

첫 번째, inp[i] + cur <= 0인 경우입니다. 이 경우에는 양수 값을 더해서 음수로 바꾸고 있기 때문에 단순히 구간에 더해서는 양수 구간을 최대한 만들 수 없습니다. 양수 구간을 최대한 만들기 위해서는 이전까지의 구간을 음수 구간으로 설정하고 지금 숫자부터 구간을 새롭게 만들어야 합니다.

두 번째, inp[i] + cur > 0이면서 cur > 0인 경우입니다. 이 경우에는 cur까지의 구간과 현재 구간을 따로 만들면 양수 구간의 개수가 늘어나기에 이전까지의 구간을 양수 구간으로 설정하고 지금 숫자부터 새롭게 구간을 만들어야 합니다.

세 번째, inp[i] + cur > 0이면서 cur < 0인 경우입니다. 이 경우에는 음수 값이 양수 값으로 변했기에 구간에 새롭게 추가하면 양수 구간의 개수가 늘어나기에 이전 구간에 현재 숫자를 추가해야 합니다.

 

2. inp[i] < 0인 경우

현재 숫자가 음수인 경우에도 나올 수 있는 경우의 수는 총 3가지입니다.

첫 번째, inp[i]+cur > 0인 경우입니다. 이 경우에는 현재 음수 값을 추가해도 양수 구간이 만들어지기에 현재 숫자를 구간에 새롭게 추가해야 합니다.

두 번째, inp[i]+cur <= 0 이면서 cur <= 0인 경우입니다. 이 경우에는 더해지는 모든 숫자가 음수이기 때문에 현재 숫자를 구간에 추가해주어 음수의 개수를 적게 만들어주어야 합니다.

세 번째, inp[i]+cur <= 0 이면서 cur > 0인 경우입니다. 이 경우에는 이전 구간은 양수 구간이며 현재 숫자를 구간에 추가하면 음수 구간으로 바뀌기 때문에 추가하지 않고 현재 숫자를 시작으로 새롭게 구간을 만들어주어야 합니다.

 

이렇게 각각의 경우에 대해 구간에 추가할지 말지 여부를 판단하면 N개의 숫자에 대해 성공적으로 파악할 수 있습니다. 구현 시 중요한 점은 구간에 추가할 때에는 누적합만을 구하면 된다는 점입니다. 문제를 해결하는 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#import <vector>
using namespace std;
typedef long long lint;
 
int T, N;
lint t;
vector< lint > inp;
 
int p;
lint cur;
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // init
        inp.clear();
        
        // input
        scanf("%d", &N);
        for(int i=0;i<N;i++) {
            scanf("%lld", &t);
            inp.push_back(t);
        }
        
        // sv
        cur = p = 0;
        for(int i=0;i<N;i++) {
            if(inp[i] > 0) {
                if(cur+inp[i] > 0) {
                    if(cur <= 0) cur += inp[i];
                    else {
                        p++;
                        cur = inp[i];
                    }
                }
                else {
                    p--;
                    cur = inp[i];
                }
            }
            
            else {
                if(cur+inp[i] > 0) cur += inp[i];
                else {
                    if(cur <= 0) cur += inp[i];
                    else {
                        p++;
                        cur = inp[i];
                    }
                }
            }
        }
        
        if(cur > 0) p++;
        else if(cur < 0) p--;
        
        
        if(p > 0) printf("YES\n");
        else printf("NO\n");
    }
}
/*
2
5
4 -1 -1 -1 -7
3
4 -1 -7
ans
NO
NO
 
1
6
3 -1 -2 9 -7 -3
ans
YES
*/
 

후기

간단한 듯 하지만 생각학게 많았던 그리디 문제였습니다. 조건을 섬세하게 설계하는 것이 중요한 문제라고 생각하며, 알고리즘 대회를 준비하는 사람들에게 추천하는 문제입니다. 제가 풀면서 만들어본 테스트케이스도 수록하였으니 문제를 풀어보면서 참고해보세요.