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

백준 2018 - 수들의 합 5

시간 제한 2초, 메모리 제한 32MB

# 조건

• 어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

# 접근 방법

• 투 포인터를 사용하여 풀어주면 된다.
• left, right 포인터, 현재까지의 합 val, 결과를 기록할 result를 모두 1로 설정해준다.
  • N 하나로 나타낼 수 있는 경우가 무조건 1개 존재하므로 result도 1로 설정해주었다.
• 이후 while 문을 left <= right and right < N인 경우에만 돌려주며, val이 N보다 작은 경우 right += 1 & val에 변경된 right만큼 넣고, 큰 경우 left만큼 val에서 빼주고 left += 1해주고, 같은 경우 result += 1 & right += 1을 해준다.
• 다만, 투 포인터를 사용한 경우 5000ms가 나오는데 다른 분들의 코드를 보니 수학적인 방법으로 접근하는 것이 훨씬 빠르게 동작한다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())

left = 1
right = 1
val = 1
result = 1
while left <= right and right < N:
    if val > N:
        val -= left
        left += 1

    else:
        if val == N:
            result += 1
        right += 1
        val += right

print(result)