[백준] 2018번 수들의 합 5 파이썬

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1

15

예제 출력 1

4

제출 답안

• n을 2로 나눈 값에 1을 더해 기준을 설정한다.
  • 연속된 값을 더할 때 2로 나눈 중간 값보다 큰 값들은 어차피 다 n보다 크기에 반까지만 비교해도 된다.
  • 그래야 탐색 시간을 줄일 수 있다.
• start, end를 각각 1로 설정하고 조건에 해당될 때 마다 start, end를 조정하면 된다.
• 마지막에 1을 더하는 이유는 n까지 while이 돌지 않기 때문에 n인 경우를 더하는 것이다.

'''
1. 아이디어
- 1부터 계속 증가시켜서 비교한다.
2. 시간 복잡도
- 
3. 변수
- num []
'''

import sys
input = sys.stdin.readline

n = int(input())

start , end = 1, 1
result, total = 0, 1

mid = (n // 2) + 1

while start != mid and end != mid + 1:
    if total < n:
        end += 1
        total += end
    elif total > n:
        total -= start
        start += 1
    else:
        result += 1
        end +=1
        total += end
print(result + 1)