[80일차][백준][누적합, 투포인트][1806]부분합

문제 설명

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

 

입력

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

 

출력

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

 

예제 입력, 예제 출력

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

2

 

 

코드 및 설명

import sys

n, s = map(int, sys.stdin.readline().split(" "))
n_arr = list(map(int, sys.stdin.readline().split(" ")))
prefix_sum = [0] * int(n+1)
check_bool = False

for i in range(1, n+1):
  prefix_sum[i] = prefix_sum[i-1] + n_arr[i-1]  

answer = 0

for i in range(1, len(prefix_sum)):
  if check_bool:
    break
  else:
    for j in range(len(prefix_sum)-i):      
      if prefix_sum[i+j] - prefix_sum[j] >= s:
        answer = i
        check_bool = True
        break
    
if not check_bool:
  answer = 0

print(answer)

 

처음 접근을 누적합으로 했으나, 계속 시간이 초과되었다. 누적합을 구하고 하나씩 순차적으로 확인해가다가 i값이 제일 낮을때 답이 나오면 break하고 끝까지 돌았는 데 답이 없다면 0으로 프린트해줄려고 했다. 근데 너무 시간이 오래걸려서 시간 초과가 된다. 그래서 투포인트 알고리즘으로 바꿔보았다.

 

import sys

n, s = map(int, sys.stdin.readline().split(" "))
n_arr = list(map(int, sys.stdin.readline().split(" ")))

left, right = 0, 0
answer = 100001
n_sum = n_arr[0]

while left <= right:  
  if n_sum >= s:
    n_sum -= n_arr[left]
    answer = min(answer, right-left+1)    
    left += 1
  else:
    right += 1
    if right < n:
      n_sum += n_arr[right]   
    else:
      break

if answer == 100001:
  answer = 0
  
print(answer)

 

왼쪽 0부터 시작해서 n_arr[0] + n_arr[1] 근데 이게 15를 넘지 않기 때문에 n_sum안에 n_arr[0] + n_arr[1] 합이 저장되고, n_arr[2]를 다시 더 하는 데 이것이 또 15를 넘지않기때문에 반복, 그리고 15를 넘는 순간 left를 1로 옮기고 다시 진행. right는 왼쪽이 0번째 일때 돌았던 4를 가지고 있고 여기서 다시 n_sum에는 1부터 3까지의 합이 들어있고 다시 더해가면서 15를 넘기는 수를 다시 비교해서 answer에 값을 저장한다. 다 돌았는 데 100001이라면 0 아니면 answer에 담긴 답을 프린트하면 된다!!!