[Algorithm] 1일1솔 - 백준 1806 부분합 (python3)

문제링크

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

1806번: 부분합

 

문제풀이

주어진 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이므로 투포인터로 풀이가 가능한 문제이다.

수열의 길이 N과 타겟으로 봐야할 S의 범위는 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 이므로 시간초과에 유의해야한다.

 

처음에는 아무 생각 없이 주어진 수열 arr의 길이를 구하는 거니까 len(arr[left:right])) 라고 썼다가 계속 시간초과가 났다.

# 시간초과 풀이
import sys
n, s = map(int, input().split())
arr = list(map(int, input().split()))

left, right, val = 0,0,0
ans = sys.maxsize

while True:
    if val < s:
        if right == n: break  # right가 끝에 도달하면 right+=1 하기 전에 break 주기
        val += arr[right]
        right += 1
    else:
        ans = min(ans, len(arr[left:right]))  # 시간초과 나는 구간
        val -= arr[left]
        left += 1
if ans == sys.maxsize:
    print(0)
else:
    print(ans)

 

len(arr[left:right]))는 리스트에서 탐색시간이 추가로 소요되기 때문에 시간복잡도가 리스트의 길이를 구하는 O(1) 외에 슬라이싱까지 하기 때문에 O(right-left) 까지 발생한다. 

따라서 해당 코드를 깔끔하게 right-left 로 변경해서 산술연산으로만 끝나게끔 해주면 시간복잡도가 O(1)로 단축된다.

# 통과풀이
import sys
n, s = map(int, input().split())
arr = list(map(int, input().split()))

left, right, val = 0,0,0
ans = sys.maxsize

while True:
    if val < s:
        if right == n: break
        val += arr[right]
        right += 1
    else:
        ans = min(ans, right-left)  # 바로 right-left 로 계산해주기
        val -= arr[left]
        left += 1
if ans == sys.maxsize:
    print(0)
else:
    print(ans)

 

나중에 부분합으로도 풀어봐야겠다.

cf) 부분합이란?
시작점과 끝점을 정해서 해당 구간 내에 있는 원소들의 합을 구하는 것

• for i in range(1, n+1):
      prefix[i] = prefix[i-1] + arr[i-1]