[알고리즘] BOJ 1806 부분합 #Python

[BOJ] 1806 부분합 바로가기

📍 문제

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

---

📍 입력

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

---

📍 출력

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

---

📍 풀이

🧷 풀이 과정

수열의 부분합을 구하기 위해 누적합과 투 포인터 기술을 사용하였습니다.

• 누적합을 사용한 이유는 더하기(+) 연산을 줄이고 한번의 빼기(-) 연산으로 수열의 특정 구간에 대한 부분합을 구할 수 있기 때문입니다.
  • 예를 들어 [1, 2, 3, 4, 5] 와 같은 리스트가 존재할 때 2번째 원소부터 5번째 원소(2, 3, 4, 5)까지의 합을 구해야 한다면 총 3번(2 + 3 + 4 + 5 = 14)의 더하기 연산을 수행해야 합니다.
  • [1, 2, 3, 4, 5] 리스트를 누적합으로 업데이트하면 [1, 3, 6, 10, 15] 와 같이 수정되고 2번째 원소부터 5번째 원소까지의 합을 구해야 한다면 5번째 원소(15)에서 1번째 원소(1)의 뺄셈(15 - 1 = 14)을 통해 부분합의 값을 구할 수 있습니다.

• 투 포인터를 사용한 이유는 한번의 탐색으로 조건(합이 S 이상이 되는 것)에 해당하는 모든 경우의 수를 확인할 수 있기 때문입니다.

✍ 전체 코드

# BOJ 1806 부분합
# https://www.acmicpc.net/problem/1806

from sys import stdin, maxsize

def solution(N, S, numbers):
    answer = maxsize

    # 누적합
    for i in range(1, N+1):
        numbers[i] += numbers[i-1]
    
    # 투 포인터
    start, end = 0, 1
    while end < N+1:
        num = numbers[end] - numbers[start]
        if num < S:
            end += 1
        else:
            answer = min(answer, end - start)
            start += 1

    return answer if answer != maxsize else 0

# input
N, S = map(int,stdin.readline().split())
numbers = [0] + list(map(int,stdin.readline().split()))

# result
res = solution(N, S, numbers)
print(res)