[코드포스] 1426 D. Non-zero Segments - 파이썬

Kolya got an integer array a1,a2,…,an The array can contain both positive and negative integers, but Kolya doesn't like 0, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be 0. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum 00. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, 0, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum 0.

 

 

📥 Input

The first line of the input contains one integer n (2≤n≤2000002≤n≤200000) — the number of elements in Kolya's array.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−10**9≤ai≤10**9,ai≠0−10**9≤ai≤10**9,ai≠0) — the description of Kolya's array.

 

📤 Output

Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum 00.

 

📖 Solution

문제를 해석해보자면,,,

배열의 개수 n과 배열이 주어졌을 때, 그 배열의 누적합이 0이 되지 않게 사이사이에 새로운 값을 넣는다고 할 때 삽입해야 하는 최소 횟수를 구하면 된다. 삽입하는 수는 아무런 수가 가능하고 무한 또한 가능하다.

 

문제 해결은 배열의 첫번째 원소부터 n번째 원소까지 하나씩 더해가면서 그 합이 0이라면 무한을 추가해주고 다시 누적합도 0으로 바꾼뒤 남은 원소를 더하갔다. 여기서 누적합을 초기화해준 이유는 무한이 껴있는 이상 누적합이 0이 될 수 없기 때문이다. 그래서 추가해준 부분 이전은 더 이상 생각하지 않아도 된다.

💻 Code

n = int(input()) # 배열의 개수
a = list(map(int,input().split())) # 배열
prefix_sum = [0]*200001 # 누적합을 저장해줄 배열
map = {} # map 자료구조
ans = 0 # 정답 변수

map[0] = 1
for i in range(n):
    prefix_sum[i] = a[i]
    if i != 0:
        prefix_sum[i] += prefix_sum[i-1] # 누적합 구함
    if prefix_sum[i] in map: # 누적값이 이전에 있다면 누적합이 0이 되어버림
        ans += 1 # 무한 추가
        map.clear() # 무한 추가하였으니 이전 값 무시하기 위해 초기화
        map[prefix_sum[i-1]]=1 # 무한 다음 원소 추가
    map[prefix_sum[i]] = 1 # 현재 원소
print(ans) # 최종적으로 무한 갯수 출력

 

🔗 Problem 

https://codeforces.com/contest/1426/problem/D

Problem - D - Codeforces