BOJ 28433게리맨더링 Python

문제

링크:https://www.acmicpc.net/problem/28433

접근

길이 N인 수열에서 구간 합이 양수인 구간의 개수가 음수인 구간의 개수를 초과하도록 구간을 나누는 문제
수열 A를 순회하며 a[i]가 음수인지 양수인지 확인하며 아래의 조건을 실행

a[i]가 양수고 이전 구간 확인
1. 양수구간
문제에서는 구간을 구하는 문제라서 이전 구간의 양수가 얼마나 크던
구간을 나누어 개수를 늘려준다
2.음수 구간
이전 구간에 a[i]를 더해서 0보다 커질경우 음수구간개수를 -1 해주고 양수구간 개수를 +1 해주어
이전 음수구간을 양수 구간으로 바꿔준다
만약 이전 구간에 a[i]를 더해도 0보다 작을경우는 구간에 포함시키지 않고 새로운 양수 구간을 만들어준다
a[i]가 음수고 이전 구간 확인
1. 음수 구간
양수 구간과는 반대로 음수 구간은 최대한 합쳐주는 게 좋으니까 이전 구간 합이 음수일 경우는
구간을 나누지 않고 계속 합쳐준다
2. 양수 구간
이전 구간이 양수고 음수인 a[i]를 더해도 구간이 양수일 때에는 양수 구간에 a[i]를 포함해 주어
음수 구간으로 나누지 않는다
만약 a[i]를 더했을 때 구간 합이 0보다 작아진다면 이전 양수 구간에 포함하지 않고 새로운 음수 구간을 만들어 준다.

코드

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    m = int(input())
    lst = list(map(int,input().split()))
    sumCount = 0  # 구간 카운트 
    ans = 0
    currentSum = 0
    for x in lst:
        if x > 0: #양수
            if currentSum >= 0:
                sumCount +=1
                currentSum = x
            elif currentSum < 0:
                if currentSum + x > 0:
                    sumCount +=2
                    currentSum += x
                else:
                    currentSum = x
                    sumCount +=1
        if x < 0: #음수
            if currentSum >= 0:
                if currentSum + x > 0:
                    currentSum += x
                else:
                    sumCount -=1
                    currentSum =  x
            elif currentSum < 0:
                currentSum += x
    if sumCount > 0:
        print('YES')
    else:
        print('NO')

결과