(Python/🥈2)백준리즘알고즘 1024번: 수열의 합

문제 바로가기 

문제:

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, sys.stdin.readline().rstrip().split(" "))

for i in range(m, 101):
    # 공차 1 등차수열 합
    x = n - (i * (i + 1) // 2)
    if x % i == 0:  # 등차수열 만족 했을때
        xx = x // i  # 연속된 자연수의 시작점
        if xx + 1 >= 0:
            print(*[i for i in range(xx + 1, xx + i + 1)])
            break
else:
    print(-1)

 

 

첫 째항 이 a 공차가 d일때의 등차수열의 공식이다 Sn = n{2a+(n-1)d} / 2 

이것을  간단히 하면 n(n+1)  / 2 가 된다.

 

근데 첫째항을 x+1 부터 해준다. 그 이유는 계산의 편의를 위해 x+1 로 해주었다.

이것을 식으로 나타내면

 

Sn = (n-1)n / 2  + x 가 된다.

 

Sn은 우리가 N으로 알기 때문에 이항해주면

Sn - ((n-1)n / 2) = x 로 나온다.

 

 

x % 2 == 0 으로 등차수열 만족을 확인하고

등차수열의 식을 사용해 시작점을 찾는다.

시작점이 0 보다 큰 경우

그 점부터의 갯수만큼 등차수열의 합으로 N을 나타낼 수 있게된다.