[백준] 1806번: 부분합

문제

백준 - 1806번: 부분합

분석

N짜리 수열이 주어지면 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이다. (s 이상의 합이 불가능하면 0을 출력)

N의 조건이 10 ≤ N < 100,000 이기 때문에 N^2의 시간 복잡도를 가지는 2중 for문은 사용할 수 없다.
이런 문제는 투 포인터의 전형적인 유형이다.
투 포인터의 흐름은 다음과 같다.

1. i, j 포인터가 둘 다 0에서 시작한다.
2. j가 문제에서 말한 조건을 만족할 때까지 1씩 증가한다. 그러면서 부분합도 갱신한다.
3. j의 전진이 불가능하다면 조건에 만족하는지 확인하고 최종답을 갱신한다.
4. i의 증가 전에 부분합에서 현재 i에 위치한 값을 뺀다.

N이 최대 10^5-1이므로 최소 길이(mn)는 10^5로 초기화 한다.
부분합이 s를 넘지 않으면 부분합에 j에 위치한 값을 더하고 j를 1 증가한다.
while 문을 빠져나왔을 때 부분합이 s 이상이면 j-i(j는 이미 1증가되어 있기 때문에 +1이 필요없음)와 mn을 비교한다.
부분합에서 i에 위치한 값을 빼준다.

모두 진행했음에도 mn 값이 초기값 그대로 라면 가능한 경우가 없는 것이므로 0을 출력한다.

투 포인터는 포인터가 수열을 한 번만 탐색하므로 O(N)의 시간 복잡도를 가진다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))
j = 0
mn = 10**5
subsum = 0
for i in range(n):
    while j < n and subsum < s:
        subsum += arr[j]
        j += 1
    if subsum >= s:
        mn = min(mn, j-i)
    subsum -= arr[i]
print(0 if mn == 10**5 else mn)

끝으로..

투 포인터를 복습할 수 있는 문제였다.