[python] 백준 2018 수들의 합 5

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

2018번: 수들의 합 5

 

문제 해결

• n = n 이므로 최소 1개는 있다.
• 연속된 수의 합을 고려
• 투 포인터를 이용하여 첫 번째 수와 마지막 수에 포인터를 두어 연속된 수의 합을 구할 수 있다.
• 왼쪽 포인터에서 오른쪽 포인터까지 합을 s라고 정의하자.
• 연속된 수의 합이 n보다 작으면 오른쪽 포인터를 오른쪽으로 이동시키고 s에 오른쪽 포인터 값을 더한다.
• 연속된 수의 합이 n보다 크면 s에서 왼쪽 포인터의 값을 빼고 왼쪽 포인터를 오른쪽으로 이동시킨다.
• 연속된 수의 합이 n과 같으면 ans를 하나 높이고 왼쪽포인터, 오른쪽 포인터 모두 오른쪽으로 이동시킨다.

 

CODE

import sys

input = sys.stdin.readline

n = int(input())
start = 1
end =1
ans = 1 # n을 미리 계산
s = 1
while end != n: # end가 n에 닿으면 끝!
    if s < n:
        end += 1
        s += end
    elif s > n:
        s -= start
        start += 1
    else:
        ans += 1
        end += 1
        s += end
print(ans)