[백준 1806번] 부분합 - python

문제 링크

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

1806번: 부분합

 

 

풀이 

- 누적합과 투포인터로 풀이하였다. 

처음엔 누적합과 이중 for문의 투포인터로 풀었더니, 시간 초과가 발생하였다. 

n의 최댓값이 100,000 이므로 시간 복잡도가 O(N^2)가 되어 시간 초과를 예상하였다. 

# 시간 초과 발생한 코드
n,s  = map(int,input().split())

data = list(map(int,input().split()))

dp = [0] * (n+1)
dp[1] = data[0]

# 누적합 
for i in range(2,n+1):
    dp[i] = data[i-1] + dp[i-1]

ans = n + 1 
for i in range(n):
	# 첫 시작 위치 고정 
    left = i
    right = i+1
	
    while left < right and right <= n:
        # 연속된 숫자들의 합 
        t = dp[right] - dp[left]
        
        # s 이상이면 연속 숫자 늘리기 중단 
        if t >= s:
            break 
        # s 미만이면 연속 숫자 늘림 
        else :
            right += 1 
    # 최소 길이 갱신 
    ans = min(ans, right-left)

if ans == n+1 :
    print(0)
else:
    print(ans)

따라서 while문 하나로 구현할 수 없을지 생각해보았다. 

left = 0, right = 1 으로 설정하여, 해당 구간에 포함된 연속된 숫자들의 합을 구하고 

s 이상이라면 구간의 길이를 갱신하고, left+ 1 을 해주었다.

-> 뒤에 해당 구간보다 더 짧은 구간이 나타날 수 있기 때문에 바로 중단하지 않는다.

s 미만이라면 right + 1 을 해서 연속된 숫자들의 길이를 늘려준다. 

n,s  = map(int,input().split())

data = list(map(int,input().split()))

dp = [0] * (n+1)
dp[1] = data[0]

# 누적합 
for i in range(2,n+1):
    dp[i] = data[i-1] + dp[i-1]

# 투포인터
left = 0 
right = 1 
ans = n + 1 

while left < right and right <= n :   
    tmp = dp[right]- dp[left]

    if tmp >= s :
        ans = min(ans, right-left)
        left += 1 
    else :
        right += 1

if ans == n+1 :
    print(0)
else:
    print(ans)