| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.
예를 들면 다음과 같다.
6 = 1 + 2 + 3
9 = 5 + 4 = 4 + 3 + 2
하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.
자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다.
출력
각 테스트 케이스에 대해서 N을 적어도 2개 이상의 연속된 자연수의 합으로 나타내는 경우의 수를 출력한다.
풀이
N의 범위가 점심을 나가서 먹고 있기 때문에 브루트포스와 같은 방법은 일단 1초 이내에 문제를 해결할 수 없다고 볼 수 있다. 연속된 수 k개의 합으로 만들어지는 수의 특징을 알아보자. a + 1부터 시작해 a + k까지 이어지는 연속된 k개의 수의 합은 이렇게 쓸 수 있다.
(a + 1) + (a + 2) + (a + 3) + ... + (a + k - 1) + (a + k)
= (a * k) + (1 + 2 + 3 + ... + k)
= (a * k) + k * (k + 1) // 2
따라서 k의 값을 적절히 정했을 때, N에서 k * (k + 1) // 2 값을 뺀 나머지가 k의 음이 아닌 배수(0을 포함)가 맞다면 그 수는 k개의 수의 연속합으로 나타낼 수 있다. 따라서 직접 연속합을 구할 필요 없이 k에 대한 연산만 쭉 실행해보면 각각의 k에 대해 가능 여부를 확인할 수 있다.
그런데 N의 범위가 20억을 넘기 때문에 단순히 k를 N까지 반복시켜보는 방법으론 해결할 수 없다. 잠깐 생각해보면 대충 1부터 k까지의 합이 N을 넘는다면 실행해볼 가치가 없다. a * k가 음수가 되어버리기 때문이다. 이 부분은 더 줄일 수 있지만 복잡하니 패스...
정답 코드
import sys
input = sys.stdin.readline
def solution():
for _ in range(int(input())):
N = int(input())
cnt = 0
k = 2
while k * (k + 1) <= N * 2:
t = N - (k * (k + 1)) // 2
if t >= 0 and t % k == 0: cnt += 1
k += 1
print(cnt)
solution()
