[백준] 1806번 부분합 - 파이썬(Python)

시간 제한	메모리 제한
0.5 초	128 MB

문제 (링크)

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

1806번: 부분합

 

나의 풀이

import sys

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

end = 0
intervalSum = arr[0]
ans = float('inf')

for start in range(n):
	while intervalSum < m and end < n:
    	end += 1
        if end == n:
        	break
		intervalSum += arr[end]
	
    if intervalSum >= m:
    	ans = min(ans, end - start + 1)
	
    intervalSum -= arr[start]

if ans == float('inf'): print(0)
else: print(ans)

 

접근방법 및 코드 설명

 

이전에 포스팅했던 2003번 수들의 합2(seongonion.tistory.com/48) 문제를 약간 변형한 문제이다.

 

제한시간이 0.5초라는 점에서 똑같이 투 포인터 알고리즘을 사용해야하는 것으로 알 수 있다. (제한시간 1초를 1억번 연산으로 이해하면 편하단다)

 

기존의 2003번 문제와는 다르게, intervalSum이 m을 초과한 상태일 때도 길이를 재주어야 한다.

 

또한, 길이를 재기 위해선 intervalSum뿐만 아니라 end의 위치를 계속 추적해줘야 하기 때문에 저번 포스팅에서와 마찬가지로 for문 내에 선언된 while문이 굉장히 중요한 포인트이다.

 

입출력 케이스에서 확인할 수 있듯이 길이는 점의 숫자를 세면 된다. 즉, 1과 2 사이의 거리는 2로 간주한다.

 

따라서 길이를 구할 땐 end - start 후, 1을 꼭 더해줘야한다.

 

반복문을 돌면서 구해지는 길이에 대하여 계속해서 최솟값으로 업데이트 해줘야한다.

 

처음에는 절대 나올 수 없는 길이인 n + 1을 ans의 초기값으로 설정했는데, 무한의 값을 정의하는 float('inf') 표현을 발견하고 이를 바로 써먹었다.

 

아마 다른 문제에서도 유용하게 써먹을 수 있는 표현일 것 같다.