백준 [2477] 수열의 합(Python3)

문제 링크 : https://www.acmicpc.net/problem/1024

1024번: 수열의 합

수학적 사고가 요구되는 문제. 뭔가 누적합을 사용할 수 있을 거 같아서 여기에 대해 1시간 정도 고민하다 도저히 안 돼서 풀이를 봤다.

 

완전 탐색

1부터 1,000,000,000까지 돌면서 각 지점에서 2부터 L까지의 합을 구한다.
총 시간 복잡도 O(N * (L - 2))로, N과 L이 최대 값일 때 시간 초과

 

완전 탐색 최적화 - 누적합 사용.

1부터 1,000,000,000까지의 누적합을 구한 뒤, 한 지점을 정하고 그 지점을 왼쪽 Index로 둬 이분 탐색 실행
O(N + NlogN) 으로 시간 초과 및 10억개의 배열을 만들기엔 메모리 초과

뭔가 누적합을 써야 할 문제는 아닌거 같은데. 이걸 어떻게 풀어야 할지 도저히 감이 안 왔다.

무언가 공식을 통해 탐색 범위를 줄일 수 있을 것 같았는데, 1시간 넘게 풀리지 않았다.
풀이를 본 결과 다음 블로그에서 놀라운 풀이를 알 수 있었다.

https://danco.tistory.com/30

[1024] 수열의 합

임의의 수 x가 있을 때, 이 수 부터 시작해 L개 이상의 수들의 합이 N을 만족하면 다음과 같이 표현할 수 있다.

N = x + (x + 1) + (x + 2) + ... + (x + L - 1)
이 수식을 좀 다듬으면
N = L * x + (1 + 2 + ... + L - 1)
x에 맞춰 항을 이항시키면 다음 수식이 나온다.
N - (1 + 2 + ... + L - 1) / L = x

이렇게 나온 x와 이 x가 나오게 한 L의 값이 갑의 범위다.

 

코드

N, L = map(int, input().split())

def calc(x):
    return x * (x + 1) // 2

for i in range(L, 101):
    temp = calc(i - 1)
    if (N - temp) // i >= 0 and (N - temp) % i == 0:
        j = (N - temp) // i
        for k in range(j, j + i):
            print(k, end = " ")
        exit(0)
print(-1)