[BOJ] Q1806 부분합

[BOJ] Q1806 부분합

Question

Language: Python

Difficulty: Gold 4

주어진 문제에서는 연속된 수들의 합이 S이상이 되는 것들 중에 해당 길이가 가장 작은 것을 구하라고 한다.

start,end 변수를 하나씩 두고 생각해보자 start=0,end=0 start~end 사이에 있는 있는 수들의 합을 S와 비교하면서 만약 부분합이 S보다 크면, start을 한칸 올리고 ==> 이 과정에서 부분합의 길이에 대해 계속 최신화를 한다. 만약 부분합이 S보다 작으면 end을 한 칸 올린다.

이렇게 하면 어느 순간 end는 마지막 까지 도달하게 되고 반복은 종료하게 된다.

이런식으로 2개의 변수를 이용해서 반복을 통해 문제를 해결하는 것이 two pointer유형이다.

Solution

def solution(N,s,nums):
    start,end=0,0
    count=100001
    sub_sum=nums[start]
    
    while True:
        if sub_sum>=s:
            count=min(end-start+1,count)
            sub_sum-=nums[start]
            start+=1

        elif sub_sum < s:
            end+=1
            if end == N:
                break
            sub_sum+=nums[end]
            
    if count == 100001:
        return 0
    else:
        return count
    
if __name__ =="__main__":
    N,s=map(int,input().split())
    nums=list(map(int,input().split()))
    print(solution(N,s,nums))