백준 2003번 - 수들의 합 2

출처 : 2003번: 수들의 합 2 (acmicpc.net)

2003번: 수들의 합 2

 

---

 

수들의 합 2 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

0.5 초

128 MB

22259

10847

7170

49.792%

문제

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을 넘지 않는 자연수이다.

출력

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

 

---

[ 문제 설명 ]

 

그림으로 설명하겠습니다.

 

그림 1 - 수들의 합 문제 해결 아이디어

그림 2 - 조건문의 순서에 대한 설명

 

---

 

[ 코드 ]

 

n, m = map(int, input().split())
numbers = list(map(int, input().split()))

left = 0
right = 0
sum = 0
res = 0

# 순서가 있어야 하는 이유가 있다. while 문이 종료되는 시점을 고려하면 이해 가능
while True:
    if sum >= m:
        sum -= numbers[left]
        left += 1

    # print(right, left)
    elif n == right:
        break

    else:
        sum += numbers[right]
        right += 1

    if sum == m:
        res += 1


print(res)

 

---

후기

 

다시 보면 이문제에 왜 시간이 들이고, 이해를 바로 못했는지

이해가 안 가는데..

참 복습의 힘이라는 게 신기할 따름입니다.