[백준/python] 1806번: 부분합

문제

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

1806번: 부분합

---

문제 요약

길이가 N인 수열을 입력 받고 연속된 수들의 부분 합의 크기가 S이상인 부분 수열 중 길이가 가장 짧은 수열의 길이를 출력한다.

+ 위 조건을 만족하는 부분합이 없다면 0을 출력한다.

---

코드

N, S = map(int, input().split())
# 수열의 길이 N, S 이상의 부분수열의 합

arr = list(map(int, input().split()))
# 수열

left = 0
right = 1
# arr의 인덱스를 가리킬 투 포인터

pre = [0] * (N + 1)
# pre[i]는 arr[i]이전 까지의 부분합

for i in range(N):
    pre[i + 1] = pre[i] + arr[i]

ans = N + 1
# 부분 합이 S이상인 부분 수열 중 가장 짧은 길이 (초기 값은 수열의 길이 + 1)
leng = 1
# 현재 구간의 길이

while right <= N:
    total = pre[right] - pre[left]
    # 현재 구간의 부분합

    if total < S:
    # 부분합이 S보다 작으면
        right += 1
        # right 포인터를 오른쪽으로 한 칸 이동
        leng += 1
        # 구간 길이 증가

    else:
    # 부분합이 S 이상이면
        if leng < ans:
        # 이전까지의 가장 짧은 길이보다 더 짧다면
            ans = leng

        left += 1
        # left 포인터를 오른쪽으로 한 칸 이동
        leng -= 1
        # 구간 길이 감소

if ans == N + 1:
# ans가 초기값 그대로라면 (조건에 만족하는 부분 수열이 없었다면)
    print(0)
else:
    print(ans)

---

코드 설명

1. arr[0]부터 arr[i] 이전까지의 부분합을 갖는 배열 pre[i]를 설정한다.

 

2. 현재 구간의 부분합이 S보다 작으면 right 포인터를, 크거나 같으면 left 포인터를 이동시킨다.

 

3. 부분합이 S이상 일 때, 이전까지 가장 짧았던 길이보다 더 짧다면 ans를 갱신한다.

 

4. right 포인터가 N을 초과하면 탐색을 종료한다.

 

5. ans가 초기 값 그대로라면, 조건에 만족하는 부분 수열이 없었다는 것이므로 0을 출력하고, 아니라면 ans를 출력한다.