[등차수열] 백준 2108 수들의 합

이번 포스팅에서는 백준 2108번 문제를 효율적으로 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 수 ( N )을 등차수열로 나타낼 수 있는 모든 경우의 수를 구하는 문제입니다. 특히 이 문제는 자기 자신을 포함한 수열을 고려하는 것을 요구합니다.

문제 분석

주어진 숫자 ( N )을 자기 자신도 포함하여 하나 이상의 자연수로 이루어진 등차수열로 나타낼 수 있는 모든 경우의 수를 찾는 것이 목표입니다. 수열의 길이가 1 이상인 등차수열을 찾는 과정에서 우리는 ( N )의 약수와 관련된 규칙을 활용할 수 있습니다.

핵심 개념

1. 등차수열이란?: 등차수열은 연속된 수들의 합입니다. 예를 들어, 1, 2, 3, 4, 5는 모두 연속된 수들이므로, 그 합은 15입니다. 이 문제에서는 어떤 수 ( N )을 연속된 자연수들의 합으로 나타낼 수 있는 방법을 찾는 것입니다.
2. 등차수열의 합 구하기: 등차수열의 합을 구할 때는 수열의 길이(즉, 몇 개의 숫자를 더할지)와 첫 번째 숫자가 중요합니다. 예를 들어, ( N )을 연속된 수들로 나타낼 때 ( k )개의 숫자를 더한다고 합시다. 이때, 수열의 첫 번째 숫자를 ( a )라고 하면, 수열의 합은 다음과 같이 계산됩니다:이 식을 간단히 하면:위 식을 변형하면 ( N )을 표현할 수 있는 수열의 길이와 첫 번째 숫자를 찾는 데 도움이 됩니다.
3. [
   N = k * (첫 번째 숫자 + 마지막 숫자) / 2
   ]
4. [
   N = a + (a + 1) + (a + 2) + ... + (a + k - 1)
   ]
5. 분수 형태로 생각하기: 위 식을 조금 다르게 보면, ( N )을 ( k )로 나누어 떨어지는지 확인하는 문제로 바뀝니다. 수열의 길이 ( k )와 첫 번째 숫자 ( a )가 주어지면, ( N )을 연속된 수들의 합으로 나타낼 수 있는지 판단할 수 있습니다.
6. 예를 들어, ( k )가 3이라면, ( N )을 3으로 나누어 보고 그 결과를 가지고 ( a )를 결정할 수 있습니다.

코드 설명

이 문제를 해결하기 위해 작성한 코드의 동작 원리를 단계별로 설명하겠습니다:

def is_decimal_half(numerator, denominator):
    result = numerator / denominator
    return result % 1 == 0.5 and numerator // denominator - denominator // 2 >= 0

N = int(input())
count = 1  # 자기 자신을 포함한 경우를 카운트하기 위해 1로 시작
for denominator in range(2, N+1):
    if denominator % 2 == 0:  # 짝수일 경우
        count += 1 if is_decimal_half(N, denominator) else 0
    elif N % denominator == 0 and N // denominator - denominator // 2 > 0:  # 홀수일 경우
        count += 1
print(count)

코드의 논리적 흐름:

1. 기본 설정: 자기 자신을 포함한 경우는 항상 유효하므로, 카운트의 초기값을 1로 설정합니다.
2. 반복문을 통한 분모 탐색:
   • ( 2 )부터 ( N )까지의 모든 수를 수열의 길이(분모)로 간주하고, 이 값을 이용해 등차수열로 표현 가능한지 확인합니다.
   • 짝수 분모 처리:
     • 짝수 분모의 경우, ( N / k )가 0.5로 끝나는지 확인합니다. 이를 위해 is_decimal_half 함수를 사용합니다.
     • 이 함수는 ( N/k )가 0.5로 끝나고, 특정 조건을 만족할 때만 카운트를 증가시킵니다. 여기서 조건은 등차수열의 첫 항이 0보다 큰지 여부입니다.
   • 홀수 분모 처리:
     • 홀수 분모의 경우, ( N )이 정확히 나누어떨어지고, 첫 항이 자연수로서 유효한지를 확인합니다. 조건을 만족하면 카운트를 증가시킵니다.
3. 최종 출력: 위의 과정을 통해 구한 가능한 모든 등차수열의 개수를 출력합니다.

결론

위 코드의 논리는 등차수열의 합과 약수의 관계를 이해하고 이를 활용하여 문제를 해결하는 데 중점을 둡니다. 이 접근 방식을 통해 우리는 효율적으로 ( N )을 등차수열로 나타낼 수 있는 모든 경우의 수를 계산할 수 있습니다. 알고리즘의 효율성뿐만 아니라 수학적 사고력도 필요로 하는 문제로, 풀이 과정을 이해하는 것이 중요합니다.