백준 1806 : 부분합 (Python)

본문 링크

import sys
input=sys.stdin.readline


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

dp=[0]*(N+1)
for i in range(1,len(L)+1):
    dp[i]=dp[i-1]+L[i-1] # 이렇게 하면 dp누적합 배열은 정렬된 상태이기 때문에 누적합이 가능하다?

start=0 ; end=0
answer=int(1e15)
while start<=end and end<=N:

    if dp[end]-dp[start]>=S:
        answer=min(answer,end-start)
        start+=1
    else:
        end+=1
if answer==int(1e15):
    print(0)
else:
    print(answer)
"""
S=15
5 - 6
5 - 9
5 - 14
5 - 24 -> 차이가 19
6 - 9
6 - 14
6 - 24 -> 차이가 18
9 - 14
9- 24 -> 차이가 15
14 - 24
14 - 31 -> 차이가 17
"""

📌 어떻게 접근할 것인가?

누적합 알고리즘을 공부중이라 일단 주어진 배열을 누적합으로 만들어 보았다.

연속된 수들의 합이 $S$ 이상일때 거리의 최소값을 구하는 문제이다.

이때 3번째 인덱스와 4번째 인덱스의 합 5+10=15 로써 거리가 2임을 알 수 있다.
가만히 보면 누적합 배열에서 24-9=15 가 됨을 확인 할 수 있다.

또한 누적합 배열은 정렬되어있기 때문에 투포인터를 사용가능하다.

따라서 start 와 end 값을 0 으로 잡아주고
누적합 배열의 차이 (start부터 end까지의 합) 을 구해줌으로써 $S$ 보다 작으면 end+1 , $S$ 보다 크면 start+1 을 해줘서 가장 짧은 길이를 구할 수 있다.

누적합 배열은 항상 정렬되어있기 때문에 이분탐색이나 투 포인터로 연결 할 수 있다는것을 명심해 두자.

✅ 코드에서 주의해야할 부분

• answer 값이 초기값과 같으면 0 을 출력한다.
• answer 값은 임의의 큰 수로 잡아준다.
• 숫자 하나만으로도 $S$ 가 될 수 있기 때문에 while 문 조건을 start<=end and end<=N 조건으로 잡는다.