[파이썬 PYTHON] 코드포스 1426D

Problem - 1426D - Codeforces

---

수열이 주어지는데, 특정 부분합이 0이 되지 않도록 하는 최소 횟수를 구하는 문제이다.

 

예로

 

1 -5 3 2

 

위와 같은 수열이 있을 때,

 

{-5, 3, 2} 의 합은 0이 되므로

 

1 -5 3 {Block} 2

위 모양 처럼 사이를 끊어놔야 하고 1번으로 충분하므로 답은 1이다.

---

 

16 -5 -11 -15 10 5 4 -4

위의 경우도 

16 -5 {Block} -11 -15 10 {Block} 5 4 {Block} -4

총 3번을 막아야 부분합이 0이 될 수 없다.

 

---

이 문제는, 구간합 알고리즘을 사용해야한다.

 

· 구간 합 알고리즘 (Prefix Sum Algorithm)

구간합 알고리즘에 의하면

 

누적합 수열을 이용해서 특정 구간의 합을 구할 수 있다.

 

누적합 수열 Sum 이 있을 때, 수열 Arr[a] ~ Arr[b] 의 합은

 

Sum[b]-Sum[a-1] 로 O(1) 복잡도로 구할 수 있다.

 

특정 위치(k위치)에서 누적합을 구했는데, 그 값이 이미 누적합 수열에서 존재(j위치)한다면

 

Sum[k]-Sum[j] = 0 이 될 수 있으므로 부분합이 0이 되는 순간임을 알 수 있다.

 

따라서, 누적합을 map의 key로써 저장해두고 조건문을 활용하면 된다.

 

# 구간합 알고리즘 사용
N = int(input())
arr = list(map(int, input().split()))

comSum = [0] * 200001
prefix_sum = {}
ans = 0

for i in range(N):
    if i == 0:
        prefix_sum[0] = "zero" # 누적합이 0이 되어도 부분합이 0이 되는 순간이므로
        prefix_sum[arr[i]] = "exist" # 첫번째 원소는 원소 값이 누적합이다.
        comSum[i] = arr[i] # 첫번째 원소는 원소 값이 누적합이다.
    else:
        sum = arr[i] + comSum[i - 1] # 직전에 저장했던 누적합 값과 원소를 더하면 누적합이다.
        comSum[i] = sum # 직전에 저장했던 누적합 값과 원소를 더하면 누적합이다.
        if sum in prefix_sum: # 누적합이 기록하고 있던 누적합 map에 존재하는 경우 부분합이 0이 되는 순간이다.
            ans += 1 
            prefix_sum.clear() # 누적합 기록을 초기화 한다.
            prefix_sum[0] = "zero" # 누적합이 0이 되어도 부분합이 0이 되는 순간이므로
            prefix_sum[arr[i]] = "exist" # 초기화 되었으니, 누적합이 아닌 원소 값을 기록한다
            comSum[i] = arr[i] # 누적합을 기록하던 배열도 초기화 시켜준다.
        else:
            prefix_sum[sum] = "exist" # 누적합 map에 누적합과 같은 값이 존재하지 않으면 계속 기록한다.
print(ans)