[BOJ] 1806 부분합 (Python3)

문제

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

입력

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

출력

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

예제

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

예제 출력 1
2

코드

import sys

n, s = map(int, input().split())
numList = list(map(int, input().split()))
answer = sys.maxsize
start, end = 0,0
sumNum = 0

while True:
    if sumNum >= s:
        answer = min(answer, end - start)
        sumNum -= numList[start]
        start += 1
        
        
    else:
        if end == n:
            break
            
        else:
            sumNum += numList[end]
            end+=1
            
if answer == sys.maxsize:
    print(0)
else:
    print(answer)

10 15
5 1 3 5 10 7 4 9 2 8      
2

문제 풀이

처음에는 이중 for문으로 풀었는데, 역시 골드난이도부터 왠만한 문제는 그냥 이중 for문 사용금지라고 생각해도 될정도로 무조건 이중 for문을 쓰면 시간초과가 난다.

그래서 이렇게 부분합이나 배열안에서 여러개의 부분집합을 구하는 유형의 문제의 경우는 투포인터를 사용하면 시간초과 당하지 않고 풀 수 있다.

투포인터는 말그대로 두개의 포인터, 보통 양쪽에서 포인터를 좁혀나가면 right, left, 나란하게 출발하면 start, end의 포인터를 사용해서 두 수를 조합하여 답을 구해낸다.

이 문제는 연속된 수의 부분합을 구하기 때문에, 포인터가 나란하게 start, end가 0을 가르키면서 시작한다.
sumNum에 해당값을 더해가면서 만약 sumNum이 s보다 크면 start 포인터를 한칸 옮겨 다음 숫자의 부분합을 구해가고, sumNum이 s보다 작다면 end포인터를 한칸 더 옮겨 해당 수의 범위를 늘려주며 찾는다.

sumNum이 s보다 클때의 end-start를 이전 answer와 min함수에 넣어 가장 최소인 end-start값을 찾아 반환하고,
만약 answer에 주었던 초깃값 sys.maxsize와 같다면 0을 출력하면 된다.