[BOJ] 1806 부분합 바로가기
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
수열의 부분합을 구하기 위해 누적합과 투 포인터 기술을 사용하였습니다.
+
) 연산을 줄이고 한번의 빼기(-
) 연산으로 수열의 특정 구간에 대한 부분합을 구할 수 있기 때문입니다.[1, 2, 3, 4, 5]
와 같은 리스트가 존재할 때 2번째 원소부터 5번째 원소(2, 3, 4, 5
)까지의 합을 구해야 한다면 총 3번(2 + 3 + 4 + 5 = 14
)의 더하기 연산을 수행해야 합니다.[1, 2, 3, 4, 5]
리스트를 누적합으로 업데이트하면 [1, 3, 6, 10, 15]
와 같이 수정되고 2번째 원소부터 5번째 원소까지의 합을 구해야 한다면 5번째 원소(15
)에서 1번째 원소(1
)의 뺄셈(15 - 1 = 14
)을 통해 부분합의 값을 구할 수 있습니다.합이 S 이상이 되는 것
)에 해당하는 모든 경우의 수를 확인할 수 있기 때문입니다.# BOJ 1806 부분합
# https://www.acmicpc.net/problem/1806
from sys import stdin, maxsize
def solution(N, S, numbers):
answer = maxsize
# 누적합
for i in range(1, N+1):
numbers[i] += numbers[i-1]
# 투 포인터
start, end = 0, 1
while end < N+1:
num = numbers[end] - numbers[start]
if num < S:
end += 1
else:
answer = min(answer, end - start)
start += 1
return answer if answer != maxsize else 0
# input
N, S = map(int,stdin.readline().split())
numbers = [0] + list(map(int,stdin.readline().split()))
# result
res = solution(N, S, numbers)
print(res)