개발공부/algorithm
[백준][python] 1806.부분합 - 이분탐색
so.py
2021. 4. 4. 16:24
- 백준 1806 부분합 Gold IV
- 문제링크
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
나의 코드
N, S = map(int, input().split())
A = list(map(int, input().split()))
sum_A = [0] * (N + 1)
for i in range(1, N + 1):
sum_A[i] = sum_A[i-1] + A[i-1]
answer = 1000001
start = 0
end = 1
while start != N:
if sum_A[end] - sum_A[start] >= S:
if end - start< answer:
answer = end - start
start += 1
else:
if end != N:
end += 1
else:
start += 1
if answer != 1000001:
print(answer)
else:
print(0)