[baekjoon] 1806 부분합 (python)

1806 부분합

문제

---

수열에서 연속된 수들의 부분합 중에서 합이 S이상 이고 길이가 가장 짧은 구간 의 길이를 구해야한다.

접근

---

간단하게 생각해봤을 때, 수열의 모든 원소들에 대해서 해당 원소로 시작하는 모든 구간을 탐색해보면 가능하긴 하다.
물론 이렇게 하면 O(N^2)로 타임아웃이 날 것이다. (0.5초의 시간 제한..)

어떤 구간의 합 이라고 하면 먼저 세그먼트 트리가 떠오르긴 하지만, 모든 구간을 명시해줘야하므로 이 문제와는 맞지 않는다.
(오히려 O(N^2 logn) 일 것 같은데?)

여기서는 간단하게 투포인터 방식으로 O(N) 안에 탐색을 끝낼 수 있다.

code

---

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

seq = list(map(int, input().split()))
s = 0
sum = 0
answer = 0

for e in range(N):
  sum += seq[e]

  while sum >= S:
    len = e - s + 1
    answer = len if answer == 0 else min(answer, len)
    sum -= seq[s]
    s += 1

print(answer)

투포인터를 쓸 때는 s든 e든 하나를 반복문에서 진행하고 그 안에서 나머지 하나를 조건에 맞게 땡겨주는(?) 방식으로 하는게 편한 것 같다.