[백준] 2003번 수들의 합 2 [Python] - 누적 합

N개의 수열과 자연수 M이 주어지면, i번째 수 부터 j번째 수 까지의 합이 M이 되는 경우의 수를 구하는 문제

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N$(1 ≤ N ≤ 10,000)$, M$(1 ≤ M ≤ 300,000,000)$이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

https://www.acmicpc.net/problem/2003

 

수열을 첫번째부터 마지막까지 더해가면서 아래 과정을 반복하면서 합이 M이 되는 순간이 있으면 카운트한다.

 

합이 M 미만일 때, 다음 원소를 더하고

합이 M 이상일 때, 현재 더해져 있는 원소들 중 가장 작은 인덱스를 지닌 원소를 합에서 뺀다.

 

while 문 + if 문

from sys import stdin
input = stdin.readline

def main():
    N, M = map(int, input().split())
    li = list(map(int, input().split()))

    s = c = i = j = 0
    while True:
        if s < M:
            if i == N: 
                break
            s += li[i]
            i += 1
        else:
            if s == M:
                c += 1
            s -= li[j]
            j += 1
    print(c)
        
if __name__ == "__main__":
    main()

 

 

for 문 + while 문 + if 문

from sys import stdin
input = stdin.readline

def main():
    N, M = map(int, input().split())
    li = list(map(int, input().split()))

    s = c = j = 0
    for i in range(N):
        s += li[i]
        while s > M:
            s -= li[j]
            j += 1
        if s == M:
            c += 1
    print(c)
        
if __name__ == "__main__":
    main()

 

예제 입력 1 

4 2
1 1 1 1

예제 출력 1 

3

예제 입력 2 

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2 

3