파이썬 알고리즘 314번 | [백준 1806번] 부분합 - 투포인터/누적합

314. 부분합

1) 어떤 전략(알고리즘)으로 해결?

• 단순하게 for문으로 체크할 수도 있겠지만 이는 이중 for문을 사용하기에 시간초과에 걸리게 된다.
• 이중 for문을 회피하고, 최적화된 시간 안에 접근할 수 있는 투포인터,누적합 방식으로 접근해야 합니다.

2) 코딩 설명

<내 풀이>

import sys
N, S = map(int,sys.stdin.readline().rstrip().split())
nums = list(map(int,sys.stdin.readline().rstrip().split()))  
record = nums[0]
lp,rp = 0,0
chk = False
res = int(1e9)

while True :   
    if record>=S : 
        chk = True
        if res > rp-lp+1 :  
            res = rp-lp+1
        record-=nums[lp]
        if lp<len(nums)-1 : 
            lp+=1 
        else : 
            break
    else : 
        if rp<len(nums)-1 : 
            rp+=1
            record+=nums[rp]
        else : 
            break

if chk : 
    print(res) 
else : 
    print(0)

<반성 점>

• 문제를 제대로 읽지 않고 임해서 자릿수를 의미한다는 것을 잘못 접근해 조금 헤맸던 점이 아쉽다!

<배운 점>

• 누적합 유형이 많이 부족해서 이 문제집(누적합)을 풀어보면서 유형을 익힐 것이다.