[백준] 2003번 > 수들의 합 2

www.acmicpc.net/problem/2003

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

 

---

풀이

단순 2중 for문을 이용하여 해당 i값과 그 오른쪽에 있는 값들을 더해 m이 되는지 비교하는 방법으로 문제를 구현했더니 python3로는 시간초과가 발생하고 pypy로 제출해야 겨우 통과할 수 있었다.

import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
answer = 0
for i in range(n):
    temp_sum = 0
    for j in range(i, n):
        temp_sum += nums[j]
        if temp_sum == m:
            answer += 1
            break
        if temp_sum > m:
            break
print(answer)

 

그래서 찾아보니 이 문제는 두 포인터를 사용하여 해결하는 문제라고 한다.

import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
start = 0
end = 1
count = 0
sum = nums[start]
if sum == m:
    count += 1
while not (start == end == n):
    if sum < m and end < n:
        sum += nums[end]
        end += 1
    else:
        sum -= nums[start]
        start += 1

    if sum == m:
        count += 1
print(count)

크게 어려운 알고리즘은 아니다. start / end 포인터를 지정하여 합이 m보다 작고 end포인터가 n보다 작으면 더해주고 end포인터를 1 증가 시키면 되는 것이다. 반대의 경우이면 합에서 빼주고 start포인터를 1 증가시켜준다. 그리고 while문의 맨 마지막에서 sum값과 m이 같은지 비교하여 주면 된다.

 

두 포인터를 사용하면 포인터를 이동시켜가기 때문에 중복값 계산을 할 필요가 없어지므로 시간 복잡도 면에서 훨씬 이득을 볼 수 있다.