[백준] 1806번 부분합 - Python

이번에 해결해 볼 문제는 백준에 있는 1806번 부분합입니다.

---

문제 설명

• 길이 N인 수열이 주어졌을 때 부분합이 주어진 S 이상이 되는 것 중 가장 짧은 길이의 부분합을 구하면 됩니다.

문제 해결 아이디어

• 부분합을 가장 빠르게 효율적으로 구할 수 있는 방법은 Two-Point 알고리즘입니다.
• 따라서 Two-Point 알고리즘을 통해 구하면 되는데 부분합의 경우의 수를 구하는 것이 아닌 부분합이 S 이상인 것 중 가장 짧은 길이를 구하는 문제라는 것을 잊으시면 안됩니다.

• 또한 해당 문제는 시간 제한이 다른 문제들보다 짧기 때문에 시간제약에 조금 더 신경써서 구해야 하므로 리스트의 일정 구간을 sum함수를 통해 구하는 것이 아니라 start와 end에 해당하는 부분을 빼거나 더하는 방법으로 부분합을 구하는 것이 적당해 보입니다.
  
  💭 직접 두 가지 방법을 비교해 본 결과 sum 함수를 사용하는 경우 시간초과가 발생합니다.

  val, end = 0, 0
  start = 0
  answer = N + 1
  
  # sum 함수 사용
  while start < N and end <= N:
      val = sum(arr[start:end])
  
      if val >= S:
          answer = min(answer, end - start)
          start += 1
      else:
          end += 1
  
  # 직접 더하거나 빼는 방법
  for start in range(N):
      while end + 1 <= N and val < S:
          val += arr[end]
          end += 1
  
      if val >= S:
          answer = min(answer, end - start)
      val -= arr[start]
  

나의 실수

해당 문제를 처음 제출했을 때 틀렸습니다를 받았습니다. 저는 end - start에서 오류를 찾을 수 있었습니다. end의 범위를 처음에 end + 1 < N으로 설정해 두어서 end - start의 최대 범위가 N이 10인 경우 9 - 0 = 9가 될 수 밖에 없었습니다.

😅 N의 최대 범위가 10이 되어야 하는데 말이죠…

그래서 이 부분을 end + 1 <= N으로 수정하여 정답을 맞힐 수 있었습니다.

문제 해결 코드

import sys

input = sys.stdin.readline

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

val, end = 0, 0
answer = N + 1

for start in range(N):
    while end + 1 <= N and val < S:
        val += arr[end]
        end += 1

    if val >= S:
        answer = min(answer, end - start)
    val -= arr[start]

if answer == N + 1:
    print(0)
else:
    print(answer)