트로이 수(Trojan Number)란?
어떤 수 n이 주어졌을 때, 이 수가 트로이 수(Trojan Number)인지 확인하는 문제를 살펴보겠습니다. 트로이 수란 완전 거듭제곱(perfect power)이 아닌 강한 수(strong number)를 의미합니다.
여기서 강한 수란, n의 모든 소인수 p에 대해 p² 역시 n의 약수가 되는 수를 말합니다. 다시 말해, 모든 소인수가 최소 두 번 이상 나타나야 한다는 뜻입니다. 모든 트로이 수는 강한 수이지만, 그 역은 성립하지 않습니다. 즉, 모든 강한 수가 트로이 수는 아니며, ab 형태로 표현할 수 없는 강한 수만이 트로이 수에 해당합니다.
예를 들어 입력이 72라면 결과는 True입니다. 72는 (6 × 6 × 2) = (6² × 2)로 표현할 수 있으며, 강한 수이면서 동시에 완전 거듭제곱이 아니기 때문입니다.
문제 해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- check_perfect_pow() 함수 정의 — n이 완전 거듭제곱인지 검사합니다.
- n이 1이면 True를 반환합니다.
- x를 2부터 √n의 정수 부분 + 1까지 순회하며 다음을 반복합니다.
- y := 2로 초기화하고, p := xy로 설정합니다.
- p ≤ n이고 p > 0인 동안:
- p == n이면 True를 반환합니다.
- y를 1 증가시키고 p = xy로 갱신합니다.
- 모든 반복이 끝나면 False를 반환합니다.
- check_strong_num() 함수 정의 — n이 강한 수인지 검사합니다.
- 소인수의 빈도를 저장할 맵(count)을 초기화합니다.
- n이 2로 나누어 떨어지는 동안 n을 2로 나누고(정수 나눗셈), count[2]를 1씩 증가시킵니다.
- i를 3부터 √n의 정수 부분 + 1까지 2씩 증가시키며, n이 i로 나누어 떨어지는 동안 n을 i로 나누고 count[i]를 1씩 증가시킵니다.
- n > 2이면 count[n]을 1 증가시킵니다.
- flag := 0으로 초기화한 뒤, count의 각 key-value 쌍을 확인하여 value가 1이면 flag := 1로 설정하고 반복을 종료합니다.
- flag가 1이면 False(강한 수가 아님), 그렇지 않으면 True를 반환합니다.
- 메인 로직 — check_perfect_pow(n)이 False이고 check_strong_num(n)이 True일 때만 true를 반환하며, 그 외의 경우에는 false를 반환합니다.
구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
from math import sqrt, pow
def check_perfect_pow(n):
if n == 1:
return True
for x in range(2, int(sqrt(n)) + 1):
y = 2
p = x**y
while p <= n and p > 0:
if p == n:
return True
y += 1
p = x**y
return False
def check_strong_num(n):
count = {i:0 for i in range(n)}
while n % 2 == 0:
n = n // 2
count[2] += 1
for i in range(3,int(sqrt(n)) + 1, 2):
while n % i == 0:
n = n // i
count[i] += 1
if n > 2:
count[n] += 1
flag = 0
for key,value in count.items():
if value == 1:
flag = 1
break
if flag == 1:
return False
return True
def isTrojan(n):
return check_perfect_pow(n) == False and check_strong_num(n)
n = 72
print(isTrojan(n))입력
72
출력
True
실행 결과 72는 6² × 2로 인수분해되는 강한 수이면서, 어떤 밑과 지수의 거듭제곱으로도 표현되지 않으므로 트로이 수임을 확인할 수 있습니다.