[백준] 1024번 수열의 합 ★★

💡문제접근

• 이틀동안 고민했던 문제였다. 어떻게 풀어나가야할지 도통 방법을 몰랐다. 2일째 되던 날에 질문게시판을 통해 접근법을 봤는데 중학교 때 배웠던 수열의 합 공식을 조금 변형하면 될 것 같다고 나와있었다.
• 고난도 문제에서 자주 나올 것 같아 이 방법은 꼭 기억해야겠다....

💡코드(메모리 : 30616KB, 시간 : 36ms)

import sys
input = sys.stdin.readline

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

x = 0
val = -1
for i in range(L, 101):
    ix = N - (i * (i+1) // 2)
    if ix % i == 0:
        val = ix // i
        if val >= -1:
            for j in range(val + 1, val + i + 1):
                print(j, end=" ")
            break
else:
    print(-1)

📌 접근법

• (x+1) + (x+2) + (x+3) + (x+4) + .... + (x+L)

 위의 수열의 길이는 L - 1 + 1 = L이 된다.

• 합이 N이고 최소 길이가 L이상이라는 조건이 있으므로

N = L × x(x가 길이 L만큼 존재) + (L × (L+1)) // 2(1부터 L까지 합)

따라서, L × x = N - (L × (L+1)) // 2이 된다.

이 때, L × x의 값이 길이 L로 나눴을 때, 나머지가 0이 된다면 음이 아닌 정수 리스트가 생길 수 있는 여지가 있다.

💡테스트케이스

입력

18 2

출력

5 6 7

• L = 2

💡소요시간 : 1day + 2h