[python] 백준 1024 번 수열의 합

백준 1024 번 수열의 합

https://www.acmicpc.net/problem/1024

문제

풀이

n, l = map(int, input().split())
from collections import deque

# l의 길이가 n보다 작거나 같을 때까지만 탐색
for length in range(l, 101):  # 최대 길이는 100으로 설정 (제약 조건이 있을 수 있음)
    # 연속된 숫자의 시작값을 구함 (n에서 l개의 숫자의 합이 되도록)
    start = (n - (length * (length - 1)) // 2) / length

    # 시작값이 자연수가 아니면 건너뜀
    if start < 0 or start != int(start):
        continue
    
    # 시작값이 0 이상이고 자연수일 때만 처리
    start = int(start)
    answer = [start + i for i in range(length)]
    
    # 조건에 맞는 경우를 찾으면 출력하고 종료
    if sum(answer) == n:
        print(*answer)
        exit()

# 만약 조건에 맞는 경우가 없으면 -1 출력
print(-1)

📌 주의

나는 이 문제를 start 를 구할 생각을 못해서 틀렸다. 나는 그냥 start 를 n//l로 하고 슬라이딩 윈도우 기법을 사용하려 했는데 더 똑똑한 방법이 있었다.
예를 들면,
n = 18
l = 4 일 때,
합은 start + start+1 + start+2 + ... 가 된다.
즉 합 = 4 x start + (0+1+2+3)

그래서 start = (n - (length * (length - 1)) // 2) / length 이렇게 된다.