[백준 1806번] 부분합

문제 링크 >> https://www.acmicpc.net/problem/1806

 

 

📋 문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다.

둘째 줄에는 수열이 주어진다.

수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

 

👈출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다.

만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

📝 풀이

import sys
input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
    
if sum(arr) < s:
  print(0)
else:
  start, end = 0, 0
  total = 0
  result = []

  for end in range(n):
    total += arr[end]
  
    while total >= s:
      result.append(end-start+1)
      total -= arr[start]
      start += 1
  print(min(result))

 

투포인터를 사용했다.

먼저 부분합을 만들 수 없는 경우는 입력받은 수열 arr의 요소를 모두 더해도 s가 되지 않는 경우이므로 이때는 0을 출력한다.

 

부분합을 만들 수 있다면 부분합을 구해본다.

포인터로 이용할 start와 end를 0으로 초기화하고 부분합을 저장할 total도 0으로 초기화한다.

그리고 부분합을 구한 경우 start와 end 사이의 길이를 저장할 result라는 빈 리스트를 선언한다.

 

end를 움직이며 total에 부분합을 더해나간다.

total이 s 이상의 값을 가지게 되면 이 경우 start와 end 사이의 길이를 구해 result에 삽입한다.

그리고 다시 total이 s 미만의 값을 가질 수 있도록 start를 움직여 total에서 값을 뺀다.

 

for문이 끝나게 되면 result에는 부분합을 만들 수 있는 경우의 길이들이 담긴다.

따라서 이들 중 가장 작은 값을 출력한다.