[Python] 백준 1806번 - 부분합 (골드 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 두 포인터
 - 누적

 

 

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을 출력하면 된다.

 

 

시간 제한

• Java 8: 1 초
• Java 8 (OpenJDK): 1 초
• Java 11: 1 초
• Kotlin (JVM): 1 초
• Java 15: 1 초

 

---

 

정렬을 해선 안되고 주어진 배열 그대로 사용하여 S를 만족하는 최소 길이의 수열을 찾는 문제였다.

 

python으로 풀 경우 sum()은 O(n)의 시간을 소요하기 때문에 반드시 시간초과가 발생하게 된다.

 

import sys
input = sys.stdin.readline

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

front, tail = 0, 0
total = data[0]
cnt = 0
while front <= tail:
    if total >= s:
        tmp = tail - front + 1
        if cnt == 0:
            cnt = tmp
        cnt = min(cnt, tmp)
        total -= data[front]
        front += 1
    else:
        if tail < n - 1:
            tail += 1
            total += data[tail]
        else:
            total -= data[front]
            front += 1
print(cnt)

 

값을 추가하며 앞과 뒤의 갚을 적절히 더하고 빼면서 누적합으로 두포인터를 사용하면 풀 수 있다.