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

문제)

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

---

def func(a, l):
    n = l - a + 1
    return int(n * (2 * a + (n - 1)) / 2)

N = int(input())
length = 2
done = False
ans = 1

for _ in ' ' * (N//2):
    if done: break

    n = N // length
    for i in range(n, 0, -1):
        if func(i, i + length - 1) <= N:
            if func(i, i + length - 1) == N:
                ans += 1
            length += 1
            break
        if i == 1: done = True
print(ans)

풀이:

 N이 주어졌을 때, N을 표현하기 위한 연속된 자연수의 길이를 length라고 한다. 그럼 연속된 자연수의 제한선은 어디일까?

바로 N을 length로 나눈 몫까지이다. 

 length가 2라면 N을 2로 나누었을 때 까지만 구하면 될것이다. 왜냐하면 (N // 2) + (N // 2 + 1) > N 이기 때문이다.

마찬가지로 3일 때에도 N을 3으로 나눈 몫까지만 구해보면 된다.

 이를 생각하며 코드를 작성해보면 N // length 부터 1까지 차례대로 살펴보며 해당 자연수들의 합이 N과 같다면 출력값에 1을 더해주고 N보다 작다면 길이를 늘려준 뒤 다시 실행해주면 된다.