1806번: 부분합

[amm0124]

문제

백준 1806번을 풀었습니다.
백준 1806 : https://www.acmicpc.net/problem/1806

설명

수열에서, 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제입니다

접근법

가장 짧은 것의 길이를 구하는 문제입니다. 즉, 조건을 만족했으면, 이후 숫자들은 볼 필요가 없습니다. 임의의 두 정수 i,j(둘다 n보다 작아야 합니다) seq[i]에서 seq[j]까지의 합이 S를 만족했다고 가정합시다. 즉 j+1 이후 인덱스는 볼 필요가 없다는 것입니다.

초기 시작부터, 조건을 만족하는 끝 점을 찾아봅시다. -> 이제, 시작 점을 점차 오른쪽으로 조건이 만족하지 않을 때까지 땡겨봅시다. 이렇게 된다면 일단 임시적으로 정답의 후보를 찾았습니다. 임시 정답을 알았으니 점점 확장해야 합니다. 끝점을 점차 오른쪽으로 더 땡깁니다. 조건이 만족하는 순간, 시작 점을 또 오른쪽으로 땡깁니다. 즉, 투포인터 - 슬라이딩 윈도우 문제입니다.

소스 코드

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

start, end = 0, 0
sum_ = arr[0]
ans = 100001

while True:
    if sum_ < S:
        end += 1
        if end == N: break
        sum_ += arr[end]
    else:
        sum_ -= arr[start]
        ans = min(ans, end - start + 1)
        start += 1
        
print(ans if ans != 100001 else 0)

마무리하며

투포인터 문제 오랜만에 풀어봤는데 재밌네요 .