[Python] BOJ / 1806번 / 부분합

1806번: 부분합

 

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이

투포인터 알고리즘을 사용하였습니다.

 

수열을 left와 right라는 이름의 포인터를 이용하여 탐색하는 방법입니다.

 

1. 우선 left, right, sum 변수를 0으로 초기화합니다.

2. 이후 while문을 반복하며 조건에 따라 아래의 코드를 수행합니다.

 - sum(현재까지 더한 부분합)이 s(조건) 이상일 경우 ans(출력값)을 더 작은 값으로 갱신시켜줍니다. 이때 부분합의 길이는 right - left를 통해 구할 수 있습니다. 이후 sum에서 arr[left] 값을 빼고 left 값을 증가시켜줌으로써 다음 부분합을 탐색합니다.

 - sum이 s보다 작을 경우에는 right 값을 sum에 더한 뒤, right 값을 증가시켜줌으로써 역시 다음 부분합을 탐색합니다.

---

import sys
input = sys.stdin.readline

def solve():
    global ans
    sum, left, right = 0, 0, 0

    while left <= right:
        if sum >= s:
            ans = min(ans, right - left)
            sum -= arr[left]
            left += 1
        else:
            if right >= n:
                break
            sum += arr[right]
            right += 1

n, s = map(int, input().split())
arr = list(map(int, input().split()))
ans = 100000

solve()
if ans == 100000:
    print(0)
else: print(ans)