알고리즘 스터디
[백준] 1806번 : 부분합 - Python(파이썬)
히치키치
2021. 5. 11. 02:39
문제
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
풀이
- 투포인터 : start 지점과 end 지점 정해 그 부분의 합 구하기
- 최소 길이 : end와 start인 index의 차가 작을 수록 최소 길이
- 기준 값과 비교 : 더 크면 앞의 원소 삭제 / 더 작으면 뒤에 원소 추가
코드
#문제 : https://www.acmicpc.net/problem/1806
import sys
N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
start, end, sum = 0, 0, 0 #시작 부분, 끝 부분, 시작 ~ 끝 부분 함
min_ = 100001
while True:
# 현재 부분 합 > = s
if sum >= S:
sum -= arr[start] # 앞에서 원소 한 개 삭제 : start의 위치 1 증가
start += 1
min_ = min(min_, end - start + 1) # 가장 작은 길이의 부분 합 : start~end까지가 현재 최소값보다 작으면 최소값 갱신
elif end == N: # end=N되면 탐색 종료
break
else: # 현재 부분 합 < s
sum += arr[end] # 뒤로 원소 1개 추가 : end 위치 1 증가
end += 1
if min_ == 100001: # 초기 min값과 같다면 sum이 S를 넘지 못한 것
min_ = 0
print(min_)