백준 1806번 부분합 - Python

아이디어

완전 탐색을 이용하면 쉽게 풀릴 문제이지만 시간제한이 걸려있어 다른 알고리즘을 사용해야한다. 누적 합 알고리즘과 투 포인터 알고리즘을 결합하여 시간 복잡도를 낮추는 방법을 선택했다.

1. 먼저 입력된 배열의 누적 합을 구한다.

2. 두 개의 포인터를 선언한다.

   • 초기에는 두 포인터 모두 첫 번째 요소를 바라보게 한다.

3. 두 개의 포인터를 기준으로 부분 합을 구한다.(start ~ end)

4. 만약 부분 합의 값이 S보다 작다면 end포인터를 오른쪽으로 한 칸 이동시켜 구간의 길이를 늘린다.

5. 만약 부분 합의 값이 S이상 이라면 현재 길이에서 더 짧은 길이를 테스트하기 위해 start포인터를 오른쪽을 한 칸 이동 시킨다. 그리고 현재 길이와 이전에 저장된 길이를 비교해 더 짧은 길이를 answer에 기억한다.

6. 3~5 과정을 while (start가 end보다 작거나 같다.) and (end포인터가 N보다 크지 않다.) 이 조건으로 반복한다.

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

prefix_sum = [0] * (N+1)
answer = 0

# 누적 합 구하기
for i in range(1, N + 1):
  prefix_sum[i] = prefix_sum[i-1] + number[i - 1]

# 투 포인터
start = 1
end = 1

while start <= end and end < N+1:
  sum = prefix_sum[end] - prefix_sum[start-1]
  if sum < S:
    end += 1
  else:
    length = end - start + 1
    if answer == 0:
      answer = length
    else:
      answer = min(length, answer)
    start += 1

print(answer)