BOJ-1806 부분합

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

문제 소개

10000 이하의 자연수로 이루어진 길이 n짜리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에 그 합이 s이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

문제 풀이

투 포인터로 풀이하였다. 투 포인터는 시작과 끝을 의미하는 두 개의 포인터를 이동시켜가며 조건을 만족하는 값을 찾는 알고리즘이다.

start와 end는 각각 부분합의 시작 인덱스와 끝 인덱스를 의미한다.

sum은 start부터 end까지의 부분합을 의미하며, cand는 정답 후보를 담는 리스트이다.

해답을 구하는 과정은 아래와 같다.

1. 입력받은 수열인 리스트 arr의 첫 원소부터 start로 삼아 탐색한다.

2. sum의 값이 s작은 동시에 end가 n보다 작은 동안 end를 1씩 가산하며 sum에 arr[end]를 가산한다.

3. sum이 s보다 같거나 큰 경우에만 더해진 원소의 수를 리스트 cand에 append()한다.

   • end가 n - 1까지 도달했음에도 불구하고 sum이 s보다 작은 경우에는 아무 동작도 하지 않는다.

4. 한 start에 대한 동작이 끝나면 start에 1을 가산한다.

일련의 동작이 끝난 후 cand의 길이가 0이라면 이것은 s를 만드는 것이 불가능함을 의미하므로 0을 출력하고, 그 외의 경우에는 min(cand)를 출력한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

n, s = map(int, input().split())
arr = list(map(int, input().split()))

end = 0
sum = 0
# 정답 후보들의 리스트
cand = []

# 인덱스 0부터 start로 하여 탐색
for start in range(n):
    # 조건을 만족하는 동안 sum에 가산
    while sum < s and end < n:
        sum += arr[end]
        end += 1
    # 후보 추가
    if sum >= s:
        cand.append(end - start)
    # start 한 칸 이동
    sum -= arr[start]

if not cand:
    print(0)
else:
    print(min(cand))