[BOJ/PYTHON] 2003. 수들의 합 2

백준 문제 링크: https://www.acmicpc.net/problem/2003

문제 요약

수열의 합이 M이 되는 경우의 수

핵심 아이디어

for문으로 수열을 돌면서 합을 구하는데, 합이 m이 되면 카운트를 올리면 된다.

풀이

# silver4-2003. 수들의 합 2

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = list(map(int, input().split()))
cnt = 0 # 합이 m이 되는 경우의 수

for i in range(n):
    # 수 하나만으로 m 만족하는 경우
    if array[i] == m: cnt += 1
    # 합으로 m 만족하는 경우
    temp_sum = array[i]
    for j in range(i + 1, n):
        temp_sum += array[j]
        if temp_sum == m:
            cnt += 1
print(cnt)

다른 풀이

• 순서대로 하나하나 합 리스트를 만들어두고, 합 리스트에서 빼는 방식도 있다.
• temp_sum[i] - temp_sum[j]은 array[j] + ... + array[i]와 동일하기에 if temp_sum[i] - temp_sum[j] == m 이면 카운트를 올려주면 된다.
• 투포인터를 사용해 현재 부분합이 m보다 작으면 오른쪽 포인터를, 크면 왼쪽 포인터를 옮기며 확인하면 된다.

실행 시간

메모리 115136KB, 시간 240ms (pypy)