[백준] 1024 - 수열의 합

문제

백준 1024번 수열의 합

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

 

 

문제 풀이

이 함수는 연속된 수의 합이 N이 되는 수열 중 그 값이 음수가 아니고 길이가 100 이하이면서 가장 최소의 길이를 가지는 배열을 구하는 것이다. 연속된 수열의 합은 공차가 1인 등차수열의 합으로 계산할 수 있다.

 

등차수열의 합

등차가 d인 등차수열의 첫째 항 x 부터 제 l항까지의 합 S는 다음과 같은 공식을 통해 구할 수 있다.

현재 l 값과 d, S 는 주어진 상황에서, x 값에 대한 식으로 정리하면 다음과 같다.

이때, x 는 음수가 아닌 정수이므로 x 값이 정수라면 x를 첫째 항으로 하는 등차수열이 존재함을 확인할 수 있다.

따라서 주어진 L 부터 시작하여 l 값을 하나씩 늘려가면서 x의 정수 여부를 확인하고, 등차수열이 존재하는 경우에 대해 출력하는 방식으로 문제를 해결할 수 있다. 

*수학 문제의 경우, 공식을 사용하여 문제를 해결할 수 있는 경우가 많다,

 

 

코드

import sys

input = sys.stdin.readline

n,l = map(int,input().split(' '))

while True:
  # l 값이 100을 초과할 경우 -1 출력 후 정지
  if l>100:
    print(-1)
    break

  # 등차수열의 합 공식
  x=n-l*(l-1)/2
  # x가 음수라면 l을 더 증가할 필요 없이 -1을 출력 후 정지
  if x<0:
    print(-1)
    break
  # x가 정수인지 확인
  if x%l==0:
    x=int(x/l)
    ans=[i for i in range(x,x+l)]
    print(*ans)
    break
  # x가 정수가 아니라면 l 값에 1을 추가
  else:
    l+=1