[백준] 2003번 수들의 합2 - 파이썬(Python)

문제 (링크)

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

2003번: 수들의 합 2

 

나의 풀이

import sys

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


intervalSum = arr[0] # m과 비교할 start ~ end까지 더한 값들
cnt = 0 # start ~ end == m 일 때를 세어줄 변수
end = 0 # end 포인터

for start in range(n):
	while intervalSum < m and end < n:
    	end += 1
        if end == n:
        	break
		
        intervalSum += arr[end]
	
    # while문을 나왔을 때는 intervalSum == m이거나 > m 일 때 or end == n일 때
    if intervalSum == m:
    	cnt += 1
	
    # intervalSum >= m 이므로, start 포인터를 옮겨주기 위해 해당 값을 빼준다
    intervalSum -= arr[start]
    
print(cnt)

 

접근 방법 및 코드 풀이

 

투 포인터 알고리즘을 공부한 뒤 연습용으로 바로 풀어본 문제이다. (seongonion.tistory.com/47?category=868991)

 

해당 알고리즘을 구현하는 많은 코드들이 있었지만, 이 방식이 제일 깔끔하게 느껴졌다.

 

중요한 점은 for 문에 있는 while 문의 내용이다.

 

처음 배웠던 구현 방식에서는 end += 1을 하기 전에 먼저 intervalSum += arr[end]를 해줬었다.

 

while intervalSum < m and end < n:
	intervalSum += arr[end]
    end += 1

 

하지만 이렇게 하니, intervalSum의 값이 m보다 크거나 같아 while문을 빠져나왔을 때, end 포인터가 원래 있어야 할 위치보다 한 칸 먼저 가 있는게 문제였다.

 

그러다보니 위의 문제를 푸는 데는 문제가 없을지 몰라도, 포인터의 위치를 계속 추적해줘야 하는 상황에서는 내 머릿속에서 상상한 end의 위치가 실제 위치와 달라 꽤 애를 먹게 되었다.

 

다행히 다른 사람들의 코드를 통해서 위와 같은 해답을 얻을 수 있었고, 투 포인터 알고리즘을 다른 문제에서 활용하는 것도 훨씬 용이해졌다.