오레 수(Ore Number)란 무엇일까요?
숫자 n이 주어졌을 때, 이 숫자가 오레 수(Ore number)인지 판별해야 합니다. 오레 수란 모든 양의 약수들의 조화평균(harmonic mean)이 정수가 되는 수를 의미하며, '조화약수(Harmonic Divisor Number)'라고도 불립니다.
예를 들어 입력이 28이라면 출력은 True입니다. 28의 약수는 [1, 2, 4, 7, 14, 28]로 총 6개이며, 이들 약수의 조화평균은 다음과 같이 계산됩니다.
H = 6 ÷ (1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28) = 3
계산 결과가 정수 3이므로 28은 오레 수입니다.
문제 해결 전략
이 문제는 세 개의 함수로 나누어 단계적으로 해결할 수 있습니다.
1. get_all_div(): 모든 약수 구하기
- 새 리스트
div를 생성합니다. i를 1부터 √n의 정수 부분까지 반복하면서, n이 i로 나누어 떨어지는 경우를 찾습니다.- n // i == i라면(완전제곱수 경계), 중복을 피하기 위해 i만 추가합니다.
- 그렇지 않으면 i와 n // i를 모두 추가합니다.
- 완성된 약수 리스트
div를 반환합니다.
2. get_harmonic_mean(): 조화평균 계산하기
div = get_all_div(n)으로 약수 목록을 가져옵니다.total을 0으로 초기화한 뒤, 각 약수마다total += n / div[i]를 누적합니다.total /= n을 적용하면 Σ(1/dᵢ)가 됩니다.length / total, 즉 k / Σ(1/dᵢ)를 반환합니다. 이것이 바로 약수들의 조화평균입니다.
3. solve(): 최종 판별
mean = get_harmonic_mean(n)을 호출합니다.- mean에서 정수 부분을 뺀 값이 0이면(즉, mean이 정수이면) True를 반환하고, 그렇지 않으면 False를 반환합니다.
구현 코드
def get_all_div(n):
div = []
for i in range(1, int(n**(0.5)) + 1):
if n % i == 0:
if n // i == i:
div.append(i)
else:
div.append(i)
div.append(n // i)
return div
def get_harmonic_mean(n):
div = get_all_div(n)
total = 0
length = len(div)
for i in range(0, length):
total += (n / div[i])
total /= n
return length / total
def solve(n):
mean = get_harmonic_mean(n)
if mean - int(mean) == 0:
return True
return False
n = 28
print(solve(n))실행 결과
입력:
28출력:
True정리
오레 수 판별의 핵심은 두 가지입니다. 첫째, 제곱근(√n)까지만 탐색해도 약수를 쌍으로 모두 찾을 수 있으므로 시간 복잡도를 O(√n)으로 줄일 수 있습니다. 둘째, 조화평균 공식 k / Σ(1/dᵢ)를 그대로 코드로 옮기면 됩니다. 참고로 1, 6, 28, 140, 270, 496, 672 등이 오레 수에 해당하며, 모든 완전수(perfect number)는 항상 오레 수라는 흥미로운 성질도 알려져 있습니다.