[구현/수학] 백준 1024 수열의 합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1024번: 수열의 합

 

 

2. 문제 풀이

 합이 N이면서, 길이가 L이상인 가장 짧은 연속된 자연수 리스트를 구해야 합니다.

 

 

반응형

 

3. 코드

# 입력
N, L = map(int, input().split())

# 탐색
for i in range(1, 500000001):
    res = 0
    for j in range(i, i+100):
        res += j
        if res == N and j-i > L:
            for k in range(i, j+1):
                print(k, end=" ")
            exit()
else:
    print(-1)

 브루트포스 식으로 들어가면... 당연히 답도 안 나올 뿐더러 시간 초과입니다.

 

(x+1) + (x+2) + (x+3) + ... + (x+n) = nx + (1+2+3+...+n)
= nx + n(n+1)/2
= N

 연속된 자연수의 합이므로, N이 x+1부터 x+n까지의 합인 수열을 구하면 됩니다.

 

nx + n(n+1)/2 = N
nx = N - n(n+1)/2

x = N/n - (n+1)/2

  자연수의 합이므로 x는 정수이며, x+1은 0이상이어야 합니다.

 

# 입력
N, L = map(int, input().split())

# 탐색
for n in range(L, 101):
    x = N/n - (n+1)/2
    if int(x) == x:
        x = int(x)
        if x + 1 >= 0:
            for i in range(x+1, x+n+1):
                print(i, end=" ")
            break
else:
    print(-1)