[백준] 1806. 부분합 - 파이썬

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

1806번: 부분합

 

풀이 1

문제 이름과 같이, Prefix Sum (부분합)을 이용하여 풀이하면 되는 문제.

설명은 다른 곳에 더 잘 설명되어 있을 테니 생략.

 

line 13 ~ 16에서 Time Complexity가 O(N^2)이라 TLE.

1부터 N까지의 공차가 1인 등차수열의 합은 n(n+1)/2 이므로.. O(N^2)

import sys
input = sys.stdin.readline
N, S = map(int, input().split())
nums = list(map(int, input().split()))
 
'''sums[i] = Sigma[k=0 to i] (nums[k])'''
sums = [nums[0]]
for i in range(1, N):
    sums.append(sums[i-1]+nums[i])
 
result = N
'''index: m ~ n 인 구간합 (S[n] - S[m-1])'''
for n in range(N):
    for m in range(n):
        if sums[n] - sums[m-1] >= S and result > n-m+1:
            result = n-m+1
 
print(result)

 

풀이 2

저렇게 Brute-Force로 구현하면 당연히 안 될 것 같으므로...

어떻게 해야 더 complexity를 줄일 수 있을까 생각하다가, Two Pointer가 떠오름.

n, m을 각각의 index pointer로 잡고, 값이 S 이상이면 n++, 값이 S 미만이면 m++를 해가며 진행하면 될 듯.

다만, 주의할 점은 -

n이 m을 넘지 않도록 주의, S 이상인 합이 생길 수 없다면 0 출력하도록 예외처리,

index 0~m까지의 합을 구하는 과정도 정상적으로 처리되도록 할 것.

 

N, S = map(int, input().split())
nums = list(map(int, input().split()))
 
'''sums[i] = Sigma[k=0 to i] (nums[k])'''
sums = [nums[0]]
for i in range(1, N):
    sums.append(sums[i-1]+nums[i])
 
result = N+1
'''index: n ~ m 인 구간합 (S[m] - S[n-1])'''
n = 0
m = 0
 
while m < N:
    if sums[m] - (0 if n <= 0 else sums[n-1]) >= S:
        if result > m - n + 1:
            result = m - n + 1
 
        if n >= m:
            m += 1
        else:
            n += 1
    else:
        m += 1
 
if result == N+1:
    result = 0
 
print(result)