부분합

백준 1806

부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이 구하기.

• 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.
• 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다.
• 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
• 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

입출력

접근 방식

: 인덱스를 활용하여 while문에서 sum함수로 부분합을 구하자. -> sum함수를 사용하면 시간초과

알게된 점

투포인터 알고리즘을 사용할 수 있다.

• while문 활용
• start, end 두개의 포인터를 두고 이를 인덱스로 사용한다.
• 처음에는 start, end = 0, 0
• 부분합이 주어진 수보다 작으면 부분합에 end번째 값 더하기 & end ++
• 부분합이 주어진 수 이상이면 end-start로 길이를 구하고 최소인지 확인 & start번째 값 빼기 & start ++
• end가 수열의 길이와 같을 때 반복문 탈출.

코드

n, s = map(int, input().split())
nums = list(map(int, input().split()))

start, end = 0, 0
mini = 1e9
sumi = 0

while True:
    if sumi>=s:
        mini = min(mini, end-start)
        sumi -= nums[start]
        start += 1
    elif end == n:
        break
    else:
        sumi += nums[end]
        end += 1

if mini == 1e9:
    print(0)
else:
    print(mini)