[백준/Python] (S2) 수열의 합 - 1024

Baekjoon Online Judge의 1024번 수열의 합 문제의 Python 풀이입니다.

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

💻코드

# 목표 합 N과 최소 길이 L을 입력받는다.
N, L = map(int, input().split())

# L부터 100까지 가능한 수열의 길이를 검사한다.
for length in range(L, 101):
    
    # 수열의 시작 값 a를 계산한다.
    a = (N - length * (length - 1) // 2) // length
    
    # 수열의 시작 값이 0 이상이어야 하고,
    # 계산된 수열의 합이 N과 일치하는지 확인한다.
    if a >= 0 and N == a * length + length * (length - 1) // 2:
        
        # 조건을 만족하는 수열을 출력한다.
        print(*range(a, a + length))
        break
else:
    # 조건을 만족하는 수열이 없으면 -1을 출력한다.
    print(-1)

🧠풀이

이 문제는 주어진 자연수 N을 특정 길이 L 이상인 연속된 음이 아닌 정수의 합으로 나타낼 수 있는지, 그리고 그 중 가장 짧은 수열을 구하는 문제이다.

주어진 수 N을 길이가 L 이상인 연속된 정수의 합으로 표현할 수 있으려면, 연속된 수열의 시작 값과 그 수열의 길이에 대해 수식을 세워 조건을 만족시키는 수열을 찾아야 한다.

연속된 정수의 합은 다음과 같은 수식으로 표현할 수 있다:

S = a+(a+1)+⋯+(a+k−1)

이때 S는 N과 같아야 하며, a는 수열의 시작 값, k는 수열의 길이이다.

수식을 정리하면:

S = k⋅a + k(k−1)/2​

여기서 S=N이므로,

N = k⋅a + k(k−1)/2​

위 식에서 a를 구하기 위해 다음과 같이 정리할 수 있다:

a = (N - k(k-1)/2)/k​​

이때 a는 0 이상의 정수이어야 하며, a로 계산된 수열이 실제 N과 일치하는지 확인해야 한다.

이 식을 이용해 L이상 100이하의 길이에 대해 가능한 가장 짧은 수열을 찾아 출력하면 된다. 만약 적합한 수열이 없다면 -1을 출력한다.

🤔느낀 점

이 문제를 풀면서 연속된 정수의 합이라는 수학적인 성질을 이해하고, 이를 이용하여 문제를 해결하는 방법에 대해 깊이 생각해볼 수 있었다.