백준: 2003 수들의 합 2

문제

2003번: 수들의 합 2

 

문제 풀이

 N 크기의 수열이 주어질 때, 수열의 부분 합 중 M을 만족하는 개수를 반환하는 문제이다. 문제를 효율적으로 풀기 위해서는 미리 1 ~ N까지의 누적합을 계산한 후에 시작, 끝 지점을 달리하며 부분합을 계산하면 된다.

 

예제 입력 1을 기준으로 합을 누적시키면 [0, 1, 2, 3, 4]와 같이 합이 누적된다. 이를 시작 끝 지점을 0, 1로 두고 조건에 따라 순차적으로 증가시켜 가며 탐색을 하면, 전체 부분합에 대한 경우의 수를 탐색할 수 있다.

 

• start : 0, end :1
  • 누적합[end] - 누적합[start] != M 이므로 end를 1 증가시킨다.
  • start : 0, end : 2
    • 누적합[end] - 누적합[start] == M 이므로 하나의 경우의 수를 찾을 수 있다.
• 이와 같이 start에 따라 경우의 수를 분류하면
  • M을 만족하는 start end는 [[0, 2], [1, 3], [2, 4]] 임을 알 수 있다.

 단순히 이중 반복문을 통해 각 경우의 수를 판단하여도 되지만, 파이썬으로는 시간 초과가 발생한다.

 

코드

from sys import stdin


if __name__ == '__main__':
    answer = 0
    start, end = 0, 1
    n, m = map(int, stdin.readline().split())
    nums = list(map(int, stdin.readline().split()))
    subtotal = [0] * (n + 1)
    for i in range(1, n + 1):
        subtotal[i] = subtotal[i - 1] + nums[i - 1]

    while start < n and end <= n:
        cur_subtotal = subtotal[end] - subtotal[start]
        if cur_subtotal == m:
            answer += 1
            start += 1
        if cur_subtotal < m:
            end += 1
        elif cur_subtotal > m:
            start += 1

    print(answer)