[Python] 백준 1806 부분합

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

1806번: 부분합

 

문제

 

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

 

해결

 

첫번 째 시도 

: 처음에는 길이가 아니라 가장 작은 값을 구하려고 했고, while문의 조건에서 틀린듯 하다

import sys

n, s = map(int, sys.stdin.readline().split()) # 길이 n의 수열, 목표값 s

lst = list(map(int, sys.stdin.readline().split()))

start = 0
end = 0
sum = 0
min_value = sys.maxsize

while start < n and end < n:
    if sum >= s:
        min_value = min(min_value, end - start)
        sum -= lst[start]
        start += 1
    else:
        sum += lst[end]
        end += 1

if min_value == sys.maxsize:
    print(0)
else:
    print(min_value)

 

두번째 시도 : 성공

 

import sys

n, s = map(int, sys.stdin.readline().split()) # 길이 n의 수열, 목표값 s

lst = list(map(int, sys.stdin.readline().split()))

start = 0
end = 0
sum = 0
min_value = sys.maxsize

while True:
    if sum >= s:
        min_value = min(min_value, end - start)
        sum -= lst[start]
        start += 1
    elif end == n:
        break
    else:
        sum += lst[end]
        end += 1

if min_value == sys.maxsize:
    print(0)
else:
    print(min_value)