[Two Pointers] Boj1806: 부분합

[Two Pointers] Boj1806: 부분합

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

문제

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

입력

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

출력

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

입출력 예제

문제 접근

1. 가장 쉬운 방법은 2중 for문을 사용하는 것이다.

import sys
si = sys.stdin.readline
N, S = list(map(int,si().split()))
N_list = list(map(int,si().split()))
ans = N+1

def cal(start):
    sum = 0
    for i in range(start,N):
        sum += N_list[i]
        if sum >= S:
            return i-start+1
    return N+1

for i in range(N):
    if cal(i) < ans:
        ans = cal(i)

if ans == N+1:
    print(0)
else:
    print(ans)

2. 하지만 2중 포문은 불필요한 계산을 반복적으로 해야하며 시간 초과를 유발한다. 그렇기 때문에 불필요한 계산을 줄여줄 수 있는 Two Pointers를 이용하여 접근해보자.

Code | Python

import sys
si = sys.stdin.readline

N, S = list(map(int,si().split()))
N_list = list(map(int,si().split()))

ans = N+1
R = -1
sum = 0

for L in range(N):
    while R+1<N and sum < S:
        R += 1
        sum += N_list[R]
    if sum >= S:
        ans = min(ans,R-L+1)
    sum -= N_list[L]

if ans == N+1:
    print(0)
else:
    print(ans)

Code Screenshot | Output