[백준 2003번] 수들의 합 2

문제

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

4 2
1 1 1 1

 

예제 출력 1

3

 

예제 입력 2

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

 

예제 출력 2

3

 

 

---

 

 

코드

 

정답 코드

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start, end = 0, 0
cnt = 0

while start < N and end < N:
    if sum(A[start:end + 1]) == M:
        cnt += 1
        end += 1
    elif sum(A[start:end + 1]) < M:
        end += 1
    else:
        start += 1

print(cnt)

 

 

• start와 end 값을 0으로 두고
• start와 end가 N보다 작을 때까지 반복문을 돌린다 (A 리스트의 길이 만큼)
• start부터 end까지 수열의 합이 M과 같으면 카운트를 하고 end 값을 1 증가시킨다
• start부터 end까지 수열의 합이 M보다 작으면 end 값을 1 증가시킨다.
• start부터 end까지 수열의 합이 M보다 크면 start 값을 1 증가시킨다.
• 반복문이 끝나고 카운트 횟수를 출력한다

 

부분 수열의 합을 보고 투 포인터를 사용하였다.

 

 

 

끝!!

 

---

[백준 2003번] 을 정리한 내용입니다.