[Python] 백준 1806번: 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

import sys
input = sys.stdin.readline


def getMinLength():
    start, end = 0, 0
    curSum = 0
    minLength = 100001

    while start < N:
        if curSum >= S:
            minLength = min(minLength, end-start)
            curSum -= nums[start]
            start += 1
        elif end >= N:
            break
        else:
            curSum += nums[end]
            end += 1

    return minLength if minLength != 100001 else 0


if __name__ == '__main__':
    N, S = map(int, input().split())
    nums = list(map(int, input().split()))

    minLength = getMinLength()

    print(minLength)

 

투포인터 유형의 문제이다. 투포인터 알고리즘은 인접한 부분합들을 특정 크기(S)로 비교해가면서 start, end라는 두 개의 인덱스(포인터)를 갱신하면서 O(N) 시간복잡도로 수열을 탐색하는 알고리즘이다. 이 문제를 풀기 위해 사용한 투포인터 알고리즘의 특징을 정리하자면 아래와 같다.

 

 - start, end는 모두 0부터 시작한다.

 - curSum은 start~end-1의 부분합을 담고 있다.

 - 따라서, start가 증가하면 curSum이 줄어들고, end가 증가하면 curSum이 증가한다.

 - start가 N 이상일 시 반복문이 종료된다.

 

 - curSum이 S 이상일 시, minLength를 갱신하며, start 값을 1 증가시킨다. 예제 입력 1 같은 경우, 아래의 사진이 이를 설명해준다.

파란색 글씨는 start, 빨간색 글씨는 end에 해당하는 원소를 뜻한다.

즉, 이렇게 함으로써 조건에 만족하면서 길이가 최소인 부분합을 찾을 수 있게 된다.

 

 - curSum < S이면서 end < N일 경우(else)에는, end 값을 1 증가시킨다.

 - curSum < S이면서 end >= N일 경우에는 즉시 반복문을 탈출시킨다. 해당 조건을 만족했을 때, start를 증가시켜도 curSum은 점점 줄어들뿐더러, end가 범위를 벗어나서 더이상 증가시킬 수도 없기 때문이다. 아래 사진을 참고하자.

맨 밑줄을 보면, end가 범위를 벗어난 상태이면서 curSum이 S보다 작은 상태이다. 이 상황에서 break를 해준 것인데, 사실은 break 하지 않고 start를 계속 증가시켜도 크게 문제될 것은 없지만, 이렇게 하면 필요없는 연산을 줄이게 되기 때문에 break를 넣어준 것이다.