[백준] 1806번 부분합 파이썬

문제

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

입력

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

출력

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

예제 입력 1 복

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1 복

2

제출답안

import sys
input = sys.stdin.readline

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

start = end = interval_sum = 0
answer = 1000001
while end <= n:
    if interval_sum >= m:
        answer = min(answer, (end - start))
        interval_sum -= data[start]
        start += 1
    elif interval_sum < m:
        if end != n:
            interval_sum += data[end]
        end += 1

if answer == 1000001:
    print(0)
else:
    print(answer)

1. n,m값과 수열을 받는다.
2. 시작, 끝 , 부분합 값을 0으로 설정한다.
3. 끝이 n 보다 작거나 같을 때 까지 while을 돈다.
   1. 부분합이 m보다 그거나 같으면 현재 부분합이 만들어진 end와 start을 뺀다.
      1. 그래야 나중에 길이를 알 수 있다.
      2. 또한 start의 값을 빼줘야 부분합이 m보다 작아진다.
      3. start을 1더해준다.
   2. 만약 부분합이 m보다 작으면 end를 증가시켜 부분합에 값을 계속 더한다.
      1. end값이 n이 아니라면 진행
      2. 부분합이 커지도록 end값에 1을 더해줌
4. 최종적으로 부분합이 되지 못했으면 answer값이 그대로이기 때문에 0을 출력하고 answer값이 다르면 부분합이 되었단 뜻으로 answer값을 출력

print 추가해서 돌려봄

import sys
input = sys.stdin.readline

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

start = end = interval_sum = 0
answer = 1000001
while end <= n:
    if interval_sum >= m:
        answer = min(answer, (end - start))
        interval_sum -= data[start]
        start += 1
        print('start', interval_sum, start)
    elif interval_sum < m:
        if end != n:
            interval_sum += data[end]
            print('end', interval_sum, end)
        end += 1

if answer == 1000001:
    print(0)
else:
    print(answer)
>
end 5 0
end 6 1
end 9 2
end 14 3
end 24 4
start 19 1
start 18 2
start 15 3
start 10 4
end 17 5
start 7 5
end 11 6
end 20 7
start 13 6
end 15 8
start 11 7
end 19 9
start 10 8
2