[Python] 1024 수열의 합

[Silver II] 수열의 합 - 1024 

[문제 링크](https://www.acmicpc.net/problem/1024)

---

💻 문제 정의

합이 N이면서 길이가 적어도 L 이상인 가장 짧은 음이 아닌 정수 수열을 구하는 문제이다.

💡 접근 및 설계

수학적인 공식을 통해 해당 문제를 해결할 수 있었다.

$x+1$부터 시작하는 길이 $i$의 수열의 합이 $N$일 때, $x+1$이 0 이상인 정수의 수열을 구하는 문제와 같다. $ix$로 정리하였을 때 $x+1$이 0 이상, $L$이 100 이하의 $i$의 최솟값을 구하는 문제가 된다.

✏️ 알고리즘 풀이

for i in range(L, 101):
    ix = N - i*(i+1)//2

    if ix % i == 0:
        x = ix // i
        if x+1 >= 0:
            print(*(i for i in range(x+1, x+i+1)))
            break

위의 수식을 코드로 옮기면 다음과 같다.

🗒️ 최종 제출 코드

# 1024 수열의 합

N, L = map(int, input().split())

for i in range(L, 101):
    ix = N - i*(i+1)//2

    if ix % i == 0:
        x = ix // i
        if x+1 >= 0:
            print(*(i for i in range(x+1, x+i+1)))
            break

else:
    print(-1)

---

💭 오늘의 회고