[BAEKJOON] 1806번: 부분합 - 파이썬(python)

문제

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

 

정말정말 고민 많이 한 문제!! 투 포인터로 풀려고 해도, 도저히 생각이 안 나 다른 사람의 코드를 봐도 이해가 안 갔었다..😨

일단, 가장 착각한건 합이 S이상이 되는 수열의 길이중 가장 짧은 것을 구하는 것인데, 난 합이 S를 넘으면서 가장 작은 수를 찾는 것으로 착각했다.. 뒤늦게 문제를 다시 이해하고 보니, 다른 사람의 코드들도 이해가 가기 시작했다.. 😭

(어쩐지 자꾸 가장 작은 수가 1 또는 0 이 될 수도 있는데 2인 것이,, 이유가 있었다..)

🌕 코드 

import sys

N, S = map(int, input().split())
numbers = list(map(int, input().split()))

left, right = 0, 0 # 두 개의 포인터는 0에서 부터 시작
sum = 0 # 합을 저장할 변수
min_length = sys.maxsize # 먼저 최대 길이로 지정

while True:
    # 만약 총 합이 S가 넘는다면, left를 하나씩 옮겨보면서 어디까지 길이가 줄어드나 확인
    if sum >= S:
        min_length = min(min_length, right - left)
        sum -= numbers[left]
        left += 1
    elif right == N:
        break
    # 만약 총합이 S를 넘지 않는다면, right 을 오른쪽으로 한칸씩 옮기며 총합이 S를 넘을때까지 더함
    else:
        sum += numbers[right]
        right += 1

if min_length == sys.maxsize:
    print(0)
else:
    print(min_length)

* right 포인터를 오른쪽으로 옮기며 총 합이 S와 같거나 커질 때까지 더한다

* 만약 S를 넘는다면 left를 한칸씩 옮기며 S보다 작아질 때까지 뺀다.

* (right-left 를 통해 길이를 구함)

* 그 중 가장 작은 길이가 min_length가 된다. 

 

열공!!