백준 1024번 파이썬 풀이!

문제 내용

문제는 N,L이 주어지고 합이 N이면서 길이가 적어도 L이상인 연속되는 수열 중 가장 짧은 수열을 구하는 문제입니다.

처음에 dfs를 써볼까..? 어케 풀지 ? 숫자가 꽤나 큰데 ? 여러가지 고민을 하다가 등차 수열이 떠오르더라고요.

등차 수열의 합 공식을 활용하면 쉽게 풀 수 있습니다.

 

문제 풀이

등차 수열의 합 공식:   합=L(2a+(L-1)d)/2  여기서 L은 수열의 길이 , a는 첫번째 항 ,d는 등차값 (연속이니 1이겠죠?)

이걸 보고 저는 고민 끝에 수열의 길이를 작은 순부터 최대 100까지로 했을 때의 첫째 항 a를 구하는 식으로 구현하려고

했습니다.

 

코드를 올리겠습니다.

import sys
input=sys.stdin.readline
 
N,L=map(int,input().split())
 
for i in range(L,101):
    Sum=0
    start=int((2*N-i**2+i)/(2*i))
    if start<0:
        continue
    for j in range(start,start+i):
        Sum+=j
    if Sum==N:
        for j in range(start,start+i):
            print(j,end=' ')
        exit()
 
print(-1)