문제 링크

문제 소개

해당 문제는 어떠한 수열을 줬을 때, 연속된 수를 골랐을 때 합이 S 이상인 조합들 중 최소 원소를 고른 조합의 원소 개수를 물어보는 문제이다.

문제 분석 및 해결책

우선 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)이기 때문에 섣불리 N을 2차 반복문을 돌리는 짓은 안해도 시간초과가 걸릴 것이다. 그럼으로 우리는 다른 방법을 찾아야 한다.

어떤 조합의 합을 볼 때, 부분합 알고리즘을 많이 사용한다. 이 부분합의 강점은 바로 한번 부분합 리스트를 만들어 놓으면 부분의 합을 한번의 계산으로 알 수 있다는 점이다.

예를 들어, [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]가 주어졌을 때, 우리는 부분합 리스트를 [0, 5, 6, 9, 14, 24, 31, 35, 44, 46, 54]와 같다. 즉, 0번째는 5이고, 0번째 부터 1번째까지의 합은 6, 0번째 부터 2번째 합은 9임을 리스트로 만들었다.

기존에 우리는 2번째부터 4번째의 합을 구하려면 직접 찾아가서 값을 더해야 했다. 하지만, 위와같이 부분합 리스트를 만들어놓는다면, 24 - 6 = 18과 같이 한번의 계산으로 알 수 있다.

하지만 우리는 부분합들 중 조건을 만족하는 최소 길이를 찾아야 하기 때문에 투 포인터를 사용해서 범위를 찾고자 할 것이다.

두 포인터를 두어서 만약 임시 부분합이 우리가 찾는 부분합보다 작을 경우 오른쪽의 포인터를 +1해주고 만약 임시 부분합이 우리가 찾는 부분합보다 많을 경우 왼쪽의 포인터를 +1해준다. 이러한 방식으로 진행하게 될 경우 우리는 정답을 알 수 있다.

최종 코드는 아래와 같다.

최종 코드

import sys


def solution():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    sequence = list(map(int, input().split()))
    subtotal = [0 for _ in range(N + 1)]

    ans = sys.maxsize
    for i in range(N):
        subtotal[i + 1] = subtotal[i] + sequence[i]
    print(subtotal)
    p1, p2 = 0, 1
    while p1 < p2 < N + 1:
        temp = subtotal[p2] - subtotal[p1]
        if temp < S:
            p2 += 1
        else:
            ans = min(ans, p2 - p1)
            p1 += 1
    if ans == sys.maxsize:
        print(0)
    else:
        print(ans)


solution()