[백준] 1024번 수열의 합, 파이썬 문제 풀이

문제

백준의 1024번 수열의 합을 찾는 문제를 해결했습니다.

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

1024번: 수열의 합

문제

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

입력

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

예시: 18 2

출력

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

예시: 5 6 7

 

 

풀이 과정

처음 생각한 풀이 방법은, 합과 개수가 주어지면 합과 개수를 나눈 몫이 중간값이 되어 수열을 이루면 해결할 수 있다고 생각했습니다. 그래서 '//' 연산자와 '%' 연산자를 이용해서 값을 구해 반복문으로 풀었습니다.문제에 주어진 테스트 케이스는 전부 해결이 되었습니다. 하지만, 제출 결과는 틀렸습니다.

문제에 주어진 조건은 2가지입니다.

• 합이 N이면서, 수열의 길이가 적어도 L 이상이다.
• 만들 수 있는 수열 중 가장 짧아야 한다.
• 연속된 음이 아닌 정수 리스트이어야 한다. (0부터 시작해야 한다.)

제가 작성한 코드는 1, 3번째 조건은 만족합니다. 모든 반례를 넣어봐도 정상적으로 동작했기 때문입니다. 제가 도출할 수 있는 결론은 가장 짧은 수열이 아니라는 것입니다. 그래서, 가장 짧은 수열을 만들 필요가 있었습니다.

 

무작정, 0부터 L개씩 확인하는 것은 비효율적이라고 생각합니다. 곰곰히 생각하다가, 고등학교 때 배운 수열의 합 공식이 생각났습니다.

n = 수열의 개수 , a1 = 첫 항, d = 등차

▲ 등차 수열의 합 공식

여기서, 이 공식의 결과인 수열의 합(N)과, 개수(L)은 주어져 있고, 연속된 수이므로 d=1 입니다. 이 공식을 통해 첫 항을 찾아, 주어진 개수(L) 만큼 수열을 진행하면 가장 짧은 수열을 찾을 수 있습니다. 다만, 첫 항이 음수일 수도 있기 때문에, 음수의 경우 abs() 함수를 활용해 양수로 바꿔줍니다.

 

이를 코드로 표현하면 다음과 같습니다.

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

result = []
temp = 0

while(1):
    """  N과 L의 몫과 나머지를 활용해 중간값으로 두고 계산하려고 했음 -> 94%에서 틀렸음 -> 모든 반례를 찾아보고 넣어도 맞게 나옴 -> "가장 짧은" 코드가 아니라고 결론
    a = N//L
    b = N%L
    if (b == 0):
        start = a - L//2
        end = a + L//2
    else:
        start = a - b + 1
        end = a + b
    """

    start = int((2*N-L*L+L)*(2*L)**(-1)) #등차수열의 합 공식을 이용해 첫 항 찾기
    end = start + L -1

    if (start < 0): #음수가 나올 경우 0부터 카운트
        start += abs(start)
        end += abs(start)

    for i in range(start, end+1):
        result.append(i)
        temp += i

    if(temp == N):
        break
    else:
        result = []
        temp = 0
        L += 1
        if (L > 100):
            result.append(-1)
            break

for k in result:
    print(k, end=" ")

 

정리

정답 비율이 25%로 꽤 낮아서 도전 정신이 생겨서 도전해 본 문제입니다. 문제를 읽고 대략적인 풀이가 구상이 되었고, 코드로 풀어나갔습니다. 뜻밖의 걸림돌이 생겨 생각보다 오랜 시간이 들었지만, 해결할 수 있어서 기쁩니다. 확실히 수학과 관련된 문제는 수학적 기본 지식이 필요하다는 것을 다시 한 번 느꼈습니다.