[파이썬/python] 투포인터 백준 2018번: 수들의 합 5

투 포인터(Two Pointers) 알고리즘

투 포인터는 1차원 배열(또는 리스트)에서 두 개의 포인터(가리키는 위치)를 조작하여 원하는 결과를 효율적으로 얻는 알고리즘. 주로 '연속된 데이터의 구간'을 처리할 때 사용.

2018: 수들의 합 5

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

• 이 문제처럼 N이 최대 10,000,000인 경우, 이중 반복문을 사용하여 모든 경우의 수를 확인하면 O(N^2)의 시간 복잡도를 가져 제한 시간(2초) 내에 통과할 수 없음. 하지만 투 포인터를 사용하면 배열을 한 번만 순회하므로 O(N)의 시간 복잡도로 문제를 해결할 수 있어 매우 효율적.
• 작동 방식: 시작점(start)과 끝점(end)을 나타내는 두 개의 변수를 설정하고, 조건에 따라 두 포인터를 요리조리 이동시키며 구간의 합이나 길이를 구함.

문제 해설 및 접근 방법

변수 설정

• start_index: 연속된 수의 시작점 (초기값: 1)
• end_index: 연속된 수의 끝점 (초기값: 1)
• current_sum: 현재 구간의 합 (초기값: 1)
• count: 경우의 수 (초기값: 1, 숫자 N 자기 자신 하나로 이루어진 경우를 미리 포함)

이동 규칙

end_index가 N에 도달할 때까지 아래의 규칙을 반복.

1. current_sum == N (정답을 찾은 경우):
   • 정답 가짓수(count)를 1 증가.
   • 새로운 경우를 찾아야 하므로 end_index를 오른쪽으로 한 칸 이동시키고, 이동한 위치의 값을 current_sum에 더해줌.
2. current_sum < N (합이 더 필요한 경우):
   • 합을 키워야 하므로 end_index를 오른쪽으로 한 칸 이동시키고, 이동한 위치의 값을 current_sum에 더해줌.
3. current_sum > N (합이 너무 큰 경우):
   • 합을 줄여야 하므로 먼저 현재 start_index의 값을 current_sum에서 뺌.
   • 그 후 start_index를 오른쪽으로 한 칸 이동.

초기 상태

SUM < N

sum < n:
	end_idx++
	sum += end_idx

SUM = N

sum == n:
	end_idx ++
	sum = sum + end_idx
	count ++

합이 15(N)가 되었으니 end_idx를 1 늘려주고 sum에 end_idx를 더해주고 count를 늘려준다.

sum += end_idx

→ 정답을 찾고 나서도 루프를 계속 돌리려면 start나 end 둘 중 하나를 무조건 움직여야 함. end_idx를 늘려가며 답을 찾았으니 이번에는 start_idx를 늘려가며 답을 찾는 과정.

SUM > N

sum > n:
	sum -= start_idx
	start_idx ++
	

SUM == N

SUM > N

 

end_idx == N이 될 때까지 반복해준다.

코드

n = int(input())
count = 1
start_index = 1
end_index = 1
sum = 1

while end_index != n:
    if sum == n:
        count += 1
        end_index += 1
        sum += end_index
    elif sum > n:
        sum -= start_index
        start_index += 1
    else:
        end_index += 1
        sum += end_index

print(count)