백준 1806번 부분합

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #투포인터

---

조건

시간 제한	메모리 제한
0.5초	128 MB

---

문제

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

출력

2

---

코드(파이썬)

import sys


n, s = map(int, sys.stdin.readline().split())
nums = tuple(map(int, sys.stdin.readline().split()))

left, right = 0, 0
MAX_LEN = 100000001
length = MAX_LEN
between = nums[0]

while left < n:
    if between >= s:
        length = min(right - left + 1, length)
        
    if between < s and right < n-1:
        right += 1
        between += nums[right]
    else:
        between -= nums[left]
        left += 1
        
print(length if length < MAX_LEN else 0)

---

특이사항

• 해결방식
  • 투포인터를 이용해 왼쪽에서 오른쪽으로 진행
  • 지금 범위의 값이 s보다 크거나 같다면 length를 최신화
  • 지금 범위의 값이 s보다 작다면 right에 1을 더함
  • 그렇지 않다면 left에 1을 더함

---

참고문헌

-