백준_1806_부분합

문제

1806번: 부분합

풀이

가장 먼저 생각나는 것은 완전탐색이다. 다만, 반복문을 이용해 모든 경우의 수을 탐색하며 조건을 만족하는 경우 O(N^4)의 시간 복잡도로 입력값이 많아지면 엄청난 시간이 걸리게 된다. 

 

이 문제는 투 포인터 알고리즘을 사용하면 해결할 수 있다. 리스트에 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 특정 값과 같을 때까지 포인터를 조작하는 기법을 투 포인터 알고리즘이라고 한다. 

 

해당 문제를 해결하는 알고리즘을 정리해보자면 다음과 같다.

1. 포인터 s는 구간의 처음을, 포인터 e는 구간의 끝을 의미한다. 부분합은 arr[s, e)에 속하는 원소들을 모두 더한 값을 의미한다.

2. 구간의 끝을 표현하는 포인터 e가 유효한 범위를 벗어날 때까지 탐색을 반복한다.

3-1. 포인터가 목표하는 값 S보다 작다면 구간의 끝을 표현하는 포인터 e를 1만큼 증가시켜 구간을 크게 한다. 

3-2. 포인터가 목표하는 값 S보다 크다면 구간의 처음을 의미하는 포인터 s를 1만큼 증가시켜 구간을 작게 한다.

코드

import sys
N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

s, e = 0, 1 # 시작과 끝의 포인트
num = sum(arr[s:e]) # [s, e) 부분 배열의 합
ans = N+1 # 부분합의 길이

while e<N:
	# e 포인트 이동
    while num<S and e<N:
        num += arr[e]
        e += 1
	
    # s 포인트 이동
    while num>=S and s<e:
        ans = min(ans, e-s) # 부분합의 길이를 저장
        num -= arr[s]
        s += 1

# 모든 원소를 더해도 목표한 S를 넘지 않는다면 ans = 0
if (ans==N+1) : ans = 0
print(ans)