1 minute read

문제

접근 방법 (이진 탐색)

연속된 수들의 합을 구해야 한다는 조건에서 prefix sum을 활용하는 문제라는 것을 파악했다. 이때, N이 100,000까지 될 수 있으므로 모든 길이 경우의 수에 대하여 iterate 하면서 찾으려면 $O(n^2)$ 시간이 필요하므로 불가능하다고 생각했다. 따라서, 더 효율적으로 iterate 할 수 있는 binary search를 사용했다.

binary search의 대상을 수열의 길이로 설정하여 mid = (start+end)/2 길이로 S 이상의 합을 구할 수 있다면 더 짧은 길이를 test 해보고, 없다면 길이를 늘려 수열의 합을 키울 수 있게 하였다.

$O(NlogN)$의 시간복잡도로 풀 수 있게 된다.

정답 코드 (이진탐색)

import sys
input = sys.stdin.readline


"""

prefix sum으로도 모든 길이에 대한 경우의 수를 구하려면 N^2이 걸림
-> 최소 길이 iteration을 binary search로 한다면 NlogN으로 구할 수 있음
"""

n,s = map(int, input().split())
nums = [0] + list(map(int, input().split()))
prefix_sum = [0]*(n+1)

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

start = 1
end = n
ans = int(1e9)
while start <= end:
  mid = (start+end)//2
  found = False
  for j in range(n+1-mid):
    sum_ = prefix_sum[j+mid] - prefix_sum[j]
    if sum_ >= s:
      found = True
      break
  #mid 길이로 s가 된다면, 더 짧은 길이 시도
  if found:
    end = mid-1
    ans = min(ans, mid)
  else:
    start = mid+1

if ans == int(1e9):
  print(0)
else:
  print(ans)

더 나은 풀이 (투 포인터)

이 문제는 사실 투 포인터를 의도했다고 한다…..

start = 0, end = 1으로 잡고 S보다 작다면 end를 뒤로 늘리고 합이 S보다 크다면 start를 당겨서 탐색하면 된다고 한다. 이렇게 풀면 $O(N)$의 시간복잡도로 해결이 가능하다.

정답 코드 (투 포인터)

import sys
input = sys.stdin.readline

n,s = map(int, input().split())
nums = [0] + list(map(int, input().split()))


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

start, end = 0,0
ans = int(1e9)
while start <= end and end<=n:
  if prefix_sum[end] - prefix_sum[start] < s:
    end += 1
  else:
    ans = min(ans,end - start)
    start += 1

if ans == int(1e9):
  print(0)
else:
  print(ans)

You May Also Enjoy