[Python] [백준] 1806번: 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

 

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

투 포인터 알고리즘을 이용하여 풀 수 있다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.

2. 현재 부분 합이 s보다 크거나 같다면, 카운트하고 start를 1 증가시킨다.

3. 현재 부분 합이 s보다 작으면, end를 1 증가시킨다.

4. 모든 경우를 확인할 때까지 2번부터 3번까지의 과정을 반복한다.

result가 처음 설정한 값인 10000이면 s보다 크거나 같은 합을 만드는 것이 불가능한 것이므로 0을 출력한다.

이외에는 result에 있는 값을 그대로 출력한다.

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
data = list(map(int, input().split()))

result = 100000
interval_sum = 0
end = 0

for start in range(n):
    while interval_sum < s and end < n:
        interval_sum += data[end]
        end += 1

    if interval_sum >= s:
        result = min(result, end - start)

    interval_sum -= data[start]

if result == 100000:
    print(0)
else:
    print(result)