[구현/수학] 백준 2003 수들의 합 2 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2003번: 수들의 합 2

 

 

 

2. 문제 풀이

 1부터 N까지 연속된 자연수의 수열에서 부분 합이 M인 구간의 수를 구하는 문제입니다.

 

2022.02.14 - [Algorithm] - [구현/수학] 백준 11659 구간 합 구하기 4 - Python

[구현/수학] 백준 11659 구간 합 구하기 4 - Python

 시간제한이 0.5초로 매우 짧습니다. 매번 구간 합을 구하면 시간 초과가 날 수 밖에 없어요.

 그 대신, '누적 합'이라는 개념을 이용해야 합니다. 누적 합은 처음부터 i까지 더한 값을 저장해두고, 누적합끼리의 뺄셈으로 구간 합을 구하는 방법입니다.

 예를 들어, 구간 i부터 j까지의 합은 [누적 합 j - 누적 합 (i-1)] 입니다. 이에 대한 자세한 설명은 위 링크에서 참조하실 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N, M = map(int, input().split())
numlist = list(map(int, input().split()))

#누적 합
sumlist = [0]
sub_sum = 0
for i in numlist:
    sub_sum += i
    sumlist.append(sub_sum)

#M이 되는 경우의 수 찾기
res = 0 #M이 되는 경우
for i in range(N+1):
    for j in range(i):
        if sumlist[i] - sumlist[j] == M:
            res += 1
print(res)

 누적 합 개념을 이용해서 구간 합이 M인 경우를 찾습니다. 효율적인 코드를 짜도, Python은 기본 연산시간이 길기 때문에 PyPy3으로 해야 통과됩니다.