백준 9421 - 소수상근수

문제 설명

입출력 및 제한사항

풀이

"소수이면서 각 자리 수의 제곱한 수를 더한 값이 1이 되는 숫자"를 찾는 문제이다.

이 문제를 두 부분으로 구분하여 접근했다.

1. 소수 판별

2. 해당 소수가 상근수인지 판별

 

먼저 소수 판별은 에라토스테네스의 체를 사용하여 n이하의 소수 리스트를 찾았다. n의 범위가 100만까지 가능하니 100만까지 순회하면서 해당 수가 소수인지를 판별하는 것은 비효율적이니 에라토스테네스의 체를 사용했다.

이후 해당 소수가 상근수인지 판별하는 것은 직접 시뮬레이션을 했는데, 여기에서는 중요하게 짚고 넘어가야 할 부분이 있다.

100만 이하의 숫자에서 각 자리수의 제곱한 수를 더한 값의 최댓값은 999999에서 9^2 + 9^2 + ... + 9^2이다. 그럼 자리수의 제곱을 더한 값은 1 ~ 486의 범위이다. 이 말은 해당 연산을 계속한다면 1로 수렴하거나 무한히 반복하거나 이 두 가지 경우의 수 밖에 없는 것이다. 해당 조건에 따라 같은 수가 반복된 경우엔 더 이상 연산을 반복하지 않아도 된다.

내 코드

def prime_list(n):
    check = [True] * (n+1)
    for i in range(2, int(n**0.5) + 1):
        if check[i]:
            for j in range(i*i, n+1, i):
                check[j] = False
            
    ret = [i for i in range(2, n+1) if check[i]]
    return ret

    
n = int(input())

prime_nums = prime_list(n)
ans = []
for i in prime_nums:
    visited = set()
    x = i

    while x != 1 and x not in visited:      # 1에 도달하거나 중복이 발생하면 탈출
        visited.add(x)
        x = sum(int(digit) ** 2 for digit in str(x))
    
    if x == 1:  ans.append(i)
    
for i in ans:
    print(i)

위에서 설명한 조건에 따라 구현하였다. n이하의 소수들을 순회하며 연산을 반복하는데, 이미 방문한 수인지를 O(1)로 확인하기 위해 set을 사용하였다. 이후 반복을 탈출했을 때 1이라면 상근수, 1이 아니라면 일반수로 판별하였다.

 

에라토스테네스의 체: O(n loglogn)

상근수 판별: O(500) -> 최악의 경우 485를 모두 순회하는 경우가 있을 수 있음(n에 대한 식으로 나타내기가 어려워서 상수로 표현)

시간 복잡도: O(n loglogn)

고찰

특별한 알고리즘이 필요했던 것이 아니라 상근수 판별을 어떻게 구현하는지가 중요했던 문제라고 생각한다. 그래도 에라토스테네스의 체는 구현 방법을 확실하게 기억해두자!