[카테부] 코테스터디 2주차 - 부분합 (백준 1806)

 

문제 유형 : 투포인터

 

투포인터 문제를 처음 풀어봤는데,, 이해하기 어려웠다.. ! ㅠㅠ

 i가 1씩 늘어날 때마다, 최대로 뻗어나갈 수 있는 j의 위치는 항상 같거나 증가하기 때문에! (i인덱스 값만큼 줄어드니까)

이 문제는 한 방향으로 두 포인터가 진행되는 투포인터 문제인 것이다.. 

하지만... 이해를 하는 것도 어려웠는데 구현은 또 다른 문제라.. 시간을 많이.. 썼다

투포인터 문제를 몇개 더 풀어보면서 익숙해져야겠다. 

 

import sys
INT_MAX = sys.maxsize

n, s = tuple(map(int, input().split()))
arr = [0] + list(map(int, input().split()))

ans = INT_MAX

sum_val = 0 # 더해줄 값
j = 0 
for i in range(1, n + 1):
    while j + 1 <= n and sum_val < s:
        sum_val += arr[j + 1]
        j += 1
    
    if sum_val < s:
        break
    
    ans = min(ans, j - i + 1)

    sum_val -= arr[i]

if ans == INT_MAX:
    ans = 0

print(ans)