[백준 알고리즘: python 3] #1024 - 수열의 합

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

 

1024번 문제는 수열의 합이라는 이름으로 소개되어 있습니다. 여기서 수열은 연속된 음의 정수가 아닌 수로 이루어진 수열로 한정되어 있고, 수열의 합이 되어야 하는 값과 최소한으로 가져야 하는 수열의 길이가 주어집니다. 문제 설명은 여기까지 하고 풀이 설명 들어갈게요!

 

Hint!

고등 수학 과정에서 등차 수열이라는 개념이 있습니다. 연속된 수로 이루어진 수열은 대표적인 등차 수열이고, 그래서 이 문제에서는 등차 수열의 성질을 이용해서 문제를 풀 수가 있습니다. 등차 수열에 대한 개념은 여기서 다루지 않을 테니 만약 모르신다면 검색을 통해 간단히 공부를 하고 오시면 될 것 같습니다!

 

여기서 사용된 연속된 수열의 성질은 두 가지 케이스로 구분해서 생각을 해볼 수 있습니다. (1) 홀수 개의 수로 이루어진 연속된 수의 수열과 (2) 짝수 개의 수로 이루어진 연속된 수의 수열입니다. 예를 들어서 간단하게 설명을 하겠습니다.

 

(1) 홀수 개의 연속된 수로 이루어진 수열의 경우에는 그 수열의 평균이 수열의 가운데에 있는 수와 같다는 점을 이용합니다. 예를 들면,

 

5 6 7 8 9

 

와 같은 수열이 있다면, 이 수열의 합은 35이고, 숫자가 다섯 개이니 평균은 7이고 가운데 수와 같습니다. 7을 중심으로 양쪽에 있는 숫자들을 각각 더하면 모두 가웃데 수의 2배와 같기 때문에 (6 + 8 = 5 + 9 = 14) 모든 홀수 개의 연속된 수의 수열은 항상 그렇습니다. 즉, 홀수 개로 연속된 수의 합으로 만들어질 수 있는 수가 있다면, 그 수는 그 홀수로 나누어질 수 있을 것입니다. 주어진 예시를 거꾸로 생각한다면, 35는 홀수인 5로 나누어 떨어질 수 있고 그 값(평균이죠?)이 7이니까, 그 수열의 가운데 수는 7이라고 할 수 있습니다. 반면, 3으로 나누면 11.6666이 나오니까 가웃데 수로 둘 수가 없겠죠? 정수가 아니니까요.

 

따라서, N이 만약 연속된 홀수 개의 수열의 합과 같을 수 있다면, N이 홀수인 수로 나누어 떨어져야 합니다. 몫이 정수가 나와야 하니까요! 이 때 몫이 수열의 가웃데 값이다. 라고 정리할 수 있겠네요.

 

(2) 짝수 개의 연속된 수로 이루어진 수열의 경우에는 그 수열의 평균이 가운데 두 수의 평균과 같다는 점을 이용합니다. 한 번 더 생각하자면, 가운데 두 수는 정수이기 때문에 이의 평균은 항상 소수 부분이 0.5가 됩니다. 즉, 짝수 개의 연속된 수열의 합으로 나타낼 수 있는 수는 그 짝수로 나누었을 때, 소수 부분이 0.5가 나오는지 확인하면 됩니다. 예를 들어,

 

6 7 8 9 10 11

 

와 같은 수열이 있다면, 이 수열의 합은 51이고 평균은 8.5 입니다. 이는 가운데 두 수인 8, 9의 평균과 같습니다. 다시 거꾸로 생각하면, 51이라는 수가 주어졌고 짝수인 8로 나누었을 때, 8.5가 나오니 평균이 8.5인 연속된 수의 합으로 표현할 수 있다고 결론 지을 수 있어요. 반면, 4로 나누면 12.75가 나오니까 4개의 연속된 수의 합으로 표현할 수 없을거에요. 평균이 12.75인 4개의 연속된 정수의 수열은 없으니까요.

 

위의 두 성질을 이용해, 수열의 최소 길이인 L부터 최대 길이인 100까지 순차적으로 N을 나눠가면서 위의 두 경우에 해당하는 수열의 길이를 찾아낸다면 순회를 멈추고 수열을 찾아주시면 됩니다. 수열을 완성하는 것은 어렵지 않으니, 스스로 해보시길 바래요! (정 모르시겠으면 코드를 봐주세요 ㅎㅎ)

 

주의할 점!

주의할 점이 있다면, 위의 방법대로 문제를 풀 때 수열에 음수가 들어가는 경우를 배제하는 것을 잊을 수 있어요. 그래서, 만약 완성된 수열에 음수가 나오게 되면 그것은 답이 아니니 예외 처리에 주의하시길 바랍니다.

 

아래의 코드로 성공하였습니다.

 

import sys

N, L = map(int, sys.stdin.readline().split())

# 홀수개의 연속된 숫자의 평균은 항상 정수이고.
# 짝수개의 연속된 숫자의 평균은 항상 정수.5 이다.
# 평균 * 연속된 숫자의 개수 = N
# 평균 = N / 연속된 숫자의 개수

results = []
for length in range(L, 101):
    if length % 2 == 1: # 홀수
        if N % length == 0: # 나누어 떨어짐, 몫이 정수
            median = int(N / length)
            min_result = median - (length - 1) // 2
            if min_result < 0: break # 수열에 음수가 포함됨.
            max_result = median + (length - 1) // 2
            for result in range(min_result, max_result+1):
                results.append(result)
            break

    elif length % 2 == 0: # 짝수
        value = N / length
        if (value - int(value)) == 0.5: # 나눈 값의 소수 부분이 0.5일 때.
            min_result = int(value - 0.5) - (length // 2 - 1)
            if min_result < 0: break # 수열에 음수가 포함됨.
            max_result = int(value + 0.5) + (length // 2 - 1)
            for result in range(min_result, max_result+1):
                results.append(result)
            break

if results:
    print(" ".join(map(str, results)))
else:
    print(-1)