문제

문제바로가기

1. 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에서 그 합이 S이상이 되는것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하여라

접근하기

1. n의 값이 100,000 까지 입력가능하기 때문에 기본 탐색 반복문을 사용하면 시간 초과로 인해 틀리게 된다 O(N^2)
2. 투포인트 알고리즘을 사용한다 포인터 방식은 크게 두 가지 방식이 있다

• 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 방식
• 두 포인터 모두 앞에서 시작하되 속도가 다르게 움직이는 방식

여기서는 후자의 방식으로 투포인터 알고리즘이 진행된다

1. left,right 포인터를 모두 0으로 초기화한다
2. right포인터를 오른쪽으로 옮겨가며 right 인덱스를 가진 요소값을 sum 변수에 더한다
3. sum이 S보다 크거나 같아질때까지 반복한다
4. 만약sum이 S이상이라면 right가 아닌 left를 한칸씩 옮기며 S보다 작아질때까지 뺀다
   5.이 때, right-left 값을 구해서 가장 짧은 길이를 update해준다

코드

import sys
input = sys.stdin.readline

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

left,right = 0,0
sum = 0
ans = 100001

while True:
    if sum >= S:
        ans = min(ans,right-left)
        sum -= nums[left]
        left += 1

    elif right == N:
        break

    else:
        sum += nums[right]
        right += 1

if ans == 100001:
    print(0)
else:
    print(ans)