[BOJ/Python3] 1806번 부분합

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

알고리즘 분류
누적 합
투 포인터

N, S = map(int, input().split())
li = list(map(int, input().split()))

left, right = 0, 0
_sum = li[0]
min_Dis = float('inf')

while 1:
    if _sum >= S: # 문제 조건에 맞는 경우 / S보다 합이 크므로 left이동, 범위 축소
        # 최소 거리 갱신
        if min_Dis > (right - left + 1):
            min_Dis = right - left + 1
        # left가 더이상 이동할 수 없을 때 right 이동
        if left == right:
            if right == N-1: break	# right 이동 불가 break
            right += 1
            _sum += li[right]
        # 위 경우가 아니면 left 이동
        else:
            _sum -= li[left]
            left += 1
        
    elif _sum < S: # 문제 조건에 맞지 않는 경우 / S보다 합이 작으므로 right이동, 범위 확대
        if right == N-1: break  # right 이동 불가 break
        
        right += 1
        _sum += li[right]
    

# 조건을 만족하는 부분합이 없다면 0
if min_Dis == float('inf'): min_Dis = 0
print(min_Dis)

문제풀이
*모든 이동은 오른쪽 방향으로
right가 움직여야 하는 상황에서 움직일 수 없는 두가지 경우가 발생하기 전까지 반복 :
index [left, right]의 부분합 _sum이 S 이상이라면
    최소 거리 갱신,
    부분합 범위 축소를 위해 포인터 이동
    left == right 이면 불가피하게 right 이동
    *** right == N-1이면 더이상 이동할 수 없으므로 break
    else: left 이동
_sum이 S 미만이면
    부분합 범위 확대를 위해 포인터 이동
    ***right == N-1이면 더 이상 이동할 수 없으므로 break
    else: right 이동

최소 거리(min_Dis)출력

***시작 포인터 설정 : left, right 모두 0으로 설정 : 리스트의 첫 수 가 S보다 큰 경우 1을 출력해야 함.