찬우의 이것저것 Chanwoo's blog

[boj 2003 python]수들의 합 2

2020-05-17

https://www.acmicpc.net/problem/2003

문제 
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을 넘지 않는 자연수이다.
입출력 예
stdin stdout
4 2
1 1 1 1		 3
10 5
1 2 3 4 2 5 3 1 1 2		 3

첫번째 예시의 경우에서 구간의 합이 2인경우는

[1, 1, 1, 1] 
 1  1        < count: 1
    1  1     < count: 2
       1  1  < count: 3

위와 같이 모두 3개이다.

start와 end를 이용해서 구간을 표시해준다.

 v (start: 0)
[1, 1, 1, 1]
 ^ (end: 0) 
 cur: 1

 v (start: 0)
[1, 1, 1, 1]
    ^ (end: 1)
cur: 2

cur가 M보다 작으면 end를 한칸 움직이고 cur가 M보다 크면 start를 한칸 움직인다. cur와 M이 같다면 count를 늘려주고 end도 한칸 이동한다.

현재 구간의 합 cur을 구하는데에는 sum(list[start:end+1])을 이용했다.

   [1, 1, 1, 1]
               ^ (end: 4)

만약 end가 배열의 크기보다 크면 모든 경우를 탐색한것이기에 탐색을 종료한다.

# 예제 1
# N, M = map(int, "4 2".split(' '))
# A = list(map(int, "1 1 1 1".split(' ')))

# 예제 2
# N, M = map(int, "10 5".split(' '))
# A = list(map(int, "1 2 3 4 2 5 3 1 1 2".split(' ')))

N, M = map(int, input().split(' '))
A = list(map(int, input().split()))

start = 0
end = 0
cur = 0
count = 0

while True:
    # print(start, end, count, A[start:end+1], sum(A[start:end+1]))
    if end >= N:
        break

    cur = sum(A[start:end + 1])

    if cur > M:
        start += 1
    else:
        if cur == M:
	        count += 1
        end += 1

print(count)

Related Posts