[백준] 부분합 - 1806번 문제 (Python)

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

1806번: 부분합

---

문제

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

입력

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

출력

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

코드 정답

import sys
input = sys.stdin.readline

# 1806
N, S = map(int, input().split())
A = list(map(int, input().split()))

# 0~n까지의 합을 구해줌
sum_A = [0] * (N + 1)
for i in range(1, N + 1):
    sum_A[i] = sum_A[i-1] + A[i-1]

# 투포인터
ans = 1000001
start = 0
end = 1

# 알고리즘
while start != N:
    if sum_A[end] - sum_A[start] >= S:
        if end - start < ans:
            ans = end - start
        start += 1

    else:
        if end != N:
            end += 1
        else:
            start += 1

# 답이 있을 때 & 없을 때
if ans != 1000001:
    print(ans)
else:
    print(0)

풀이

1. 입력 조건에 맞춰 첫 행에 입력되는 값들을 각각 N과 S에 저장하고 두번째 행에 입력되는 값들을 리스트 형태로 묶어 A에 저장을 한다.
2. 값 0이 저장된 인덱스를 n+1개 만들어내 sum_A에 저장하고 인덱스 번호 1번부터 N번까지 A리스트 0번부터 N-1번까지의 합을 저장한다.
3. 투포인터를 이용하기 위해 start와 end라는 변수에 각각 0과 1을 저장해주었고 답이 없을 때를 확인하기 위하여 ans에 100001값을 먼저 저장해둔다.
4. start 값이 N과 같지 않다면 20~29행이 반복실행된다. 반복이 되면서 if조건문을 토대로 적합한 문장을 찾아 실행되게 되고, 그런 과정에서 start와 end 그리고 ans값이 바뀌게 된다.
5. while문과 if문을 진행하며 ans값이 바뀌어 100001 값이 아니라면 ans에 저장된 값을 출력하고 100001이 그대로라면 0을 출력한다.