[백준, BOJ] 1806 - 부분합

1. Question

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

1.1 Input

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

1.2 Output

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

1.3 Example

입력	출력
10 15 5 1 3 5 10 7 4 9 2 8	2

2. Approach

투 포인터 문제다.

부분합과 S의 관계에 따라 두 포인터를 움직이고 부분합이 S보다 클 때, p2와 p1의 차이만큼을 계산하여 최소값을 찾는다.

 

3. Submission

4. Code

import sys
rl = sys.stdin.readline

N, S = map(int, rl().split())

nums = list(map(int, rl().split()))

p1 = 0
p2 = 0

pSum = nums[0]
ans = sys.maxsize
while not(p2 >= N-1 and pSum < S):
    if pSum < S:
        p2 += 1
        pSum += nums[p2]
    else:
        ans = min(ans, p2 - p1 + 1)
        pSum -= nums[p1]
        p1 += 1
        
if ans == sys.maxsize: ans = 0
print(ans)