백준: 1860 부분합

문제

1806번: 부분합

 

문제 풀이

 앞서 다룬 수들의 합 2와 유사한 문제이다. 다른 점이 있다면 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이다. 수들의 합 2와 마찬 가지로 사전에 누적합에 대한 값을 계산하고 시작, 끝 지점을 달리하여 순차적으로 탐색을 진행하면 경우의 수를 계산할 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    answer = None
    start, end = 0, 1
    n, s = map(int, stdin.readline().split())
    nums = list(map(int, stdin.readline().split()))
    subtotal = [0] * (n + 1)
    for i in range(1, n + 1):
        subtotal[i] = subtotal[i - 1] + nums[i - 1]

    while start < n:
        if subtotal[end] - subtotal[start] >= s:
            answer = min(answer, end - start) if answer else end - start
            start += 1
        elif end == n:
            start += 1
        else:
            end += 1

    print(answer if answer else 0)