[79일차][백준][누적합][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을 넘지 않는 자연수이다.

 

출력

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

 

예제 입력, 예제 출력

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

 

 

코드 및 설명

import sys

n, m = map(int, (sys.stdin.readline().split(" ")))
x_arr = list(map(int, (sys.stdin.readline().split(" "))))
prefix_sum = [0] * int(len(x_arr)+1)

for i in range(1, len(x_arr)+1):
  prefix_sum[i] = prefix_sum[i-1] + x_arr[i-1]

count = 0
for i in range(n):
  for j in range(i+1, n+1):
    if prefix_sum[j] - prefix_sum[i] == m:
      count += 1
      
print(count)

 

이 문제는 누적합, 투 포인트로 풀 수 있다. 첫째 줄에 N은 수열의 개수를 나타내고 M은 수열의 합이 M이 되는 조건을 찾기 위해 제공되며, 두번째 줄은 수열을 나타낸 것이다.

일단 prefix_sum에 x_arr+1만큼 누적합을 구해준다. [0, 1, 2, 3, 4] 이 저장될 것이고, 수열의 합이 m= 2가 되는 것을 구하기 위해선, 수열 한 개 ~ 수열의 길이만큼의 조합을 차례로 하여 2가 되는 합을 카운트 하면 된다.

 

i = 0일 때

j = i + 1 이고, 

prefix_sum[1] - prefix_sum[0] => 1 - 0 = 1

prefix_sum[2] - prefix_sum[0] => 2 - 0 = 2

prefix_sum[3] - prefix_sum[0] => 3 - 0 = 3

prefix_sum[4] - prefix_sum[0] => 4 - 0 = 4

 

여기선 2가 되는 값이 1개이기때문에 1개 카운트

 

i = 1일때,

j = i +1

prefix_sum[2] - prefix_sum[1] => 2 - 1 = 1

prefix_sum[3] - prefix_sum[1] => 3 - 1 = 2

prefix_sum[4] - prefix_sum[1] => 4 - 1 = 3

 

2가 되는 값이 1개 -> count = 2

 

i = 2일 때

prefix_sum[3] - prefix_sum[2] => 3 - 2 = 1

prefix_sum[4] - prefix_sum[2] => 4 - 2 = 2

 

2가 되는 값이 1개 -> count = 3

 

i = 3일 때

prefix_sum[4] - prefix_sum[3] => 4 - 3 = 1

 

여기선 2가 되는 값이 없기 떄문에 count는 그대로 3

 

답은 3이 된다.

누적합을 구하고 경우의 수를 투 포인트 알고리즘을 이용하여 확인을 한 것이다.

0 1 2 3 4

i = 0을 기준으로 한 칸씩 오른쪽으로 움직인다.

0 1 -> 0 2 -> 0 3 -> 0 4

그리고 다 돌면 다시 i를 오른쪽으로 이동

1 2 -> 1 3 -> 1 4

이걸 반복하면서 경우의 수를 만들고, 2가 되는 합을 구하는 것