[BOJ]1024. 수열의 합

문제:

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

입력:

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

출력:

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

풀이방법:

 처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.

 하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.

import copy
N, L = map(int,input().split())
 
list_ = list(range(1,L+1))
start, end = 1,L
answer = [0]*100
while list_[0] <= N//2:
    if sum(list_) == N:
        if len(list_) < len(answer):
            answer = copy.deepcopy(list_)
            list_.pop(0)
    elif sum(list_) < N:
        list_.append(end)
        end+= 1
    else:
        list_.pop(0)
        start+= 1
if len(answer) > 100 or len(answer) < L:
    print(-1)
else:
    print(*answer)

따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다. 

우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.

 

N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)

 

이를 정리하면 다음과 같이 표현할 수 있다.

 

N = LX + (1+2+3+...+L-1)

   = LX + (L-1)L/2

 

그럼 X는 다음과 같이 구할 수 있다.

 

X = N/L - (L-1)/2

 

따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.

N, L = map(int,input().split())
 
answer = -1
while True:
    if L > 100:
        break
    temp = N/L-(L-1)/2
    if temp < 0:
        L+=1
        continue
    if int(temp) == temp:
        answer = int(temp)
        break
    L+=1
if answer >= 0:
    print(*range(answer,answer+L))
else:
    print(-1)

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

1024번: 수열의 합