부분합 [백준 1806] - python

import sys
input = sys.stdin.readline

def BOJ1806() :
  N, S = map(int, input().split())
  l = list(map(int, input().split()))

  f_p = 1
  s_p = 0
  result = 1e10

  s = [0, l[0]]
  for i in range(1, len(l)) :
    s.append(l[i] + s[i])

  if S > s[-1]:
    print(0)
    return

  while f_p <= N and s_p <= N :
    if s[f_p] - s[s_p] >= S :
      result = min(result, f_p - s_p)
      s_p += 1
      if f_p == s_p :
        f_p += 1
    else :
      f_p += 1

  print(result)

BOJ1806()

 

풀이 접근 방법 :

1. 처음엔 굉장히 난감했지만 의외로 쉽게 풀 수 있었던 문제였다.

2. 이전에 누적합을 통해 구간의 길이를 구했던 것이 기억나서 우선 배열을 순회하면서 하나씩 누적합을 해주었다.

3. 구간을 구하는 것이므로 포인터 두개를 적용하였다. 
첫번째 포인터를 하나씩 전진시키고 이때 구간의 합을 계속 비교한다. 

구간의 합은 누적합 배열에서 첫번째 포인터와 두번째 포인터의 인덱스 값을 빼주면 된다.

4. 구간의 합이 부분합 S보다 작을 경우에는 첫번째 포인터를 계속 전진시키고 

부분합 S보다 클 경우에는 더 작은 구간을 알아보아야 하므로 두번째 포인터를 전진 시킨다.

이때 두개의 포인터가 같은 경우는 비교할 필요가 없으므로 무조건 첫번째 포인터가 두번째 포인터보다 크게 해준다.

 

 

https://www.acmicpc.net/problem/1806

1806번: 부분합