STUDY/Algorithm

[백준] 9421 소수상근수 python

sinawi95 2022. 2. 6. 12:44
728x90

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

 

9421번: 소수상근수

양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 =

www.acmicpc.net

소수인 상근수를 찾는 문제이다.

소수를 에라토스테네스의 체로 구해놓고 소수가 상근수인지 찾으면 된다.

from math import isqrt
def findPrime(N):
    prime = [1 for _ in range(N + 1)]
    prime[0] = prime[1] = 0
    for i in range(2, isqrt(N) + 1):
        if prime[i]:
            for j in range(i + i, N + 1, i):
                prime[j] = 0
    return prime

def sanggn(n):
    visit = [0 for _ in range(100*7)]
    tmp = 0
    while 1:
        while n:
            tmp += (n % 10) ** 2
            n //= 10

        if tmp == 1:
            return True

        if visit[tmp]:
            return False
        visit[tmp] = 1
        n = tmp
        tmp = 0

def main():
    n = int(input())
    prime = findPrime(n)
    answer = []
    for i in range(2, n + 1):
        if prime[i] and sanggn(i):
            answer.append(i)

    print('\n'.join(map(str, answer)))


if __name__ == "__main__":
    main()

 

여기에서 visit을 함수 내에서 계속 초기화하면서 사용했는데 얘를 글로벌 변수로 사용하고 해당 수가 상근 수인지 아닌지 DP 형식으로 하면 시간을 더 줄일수 있을것같다.

'STUDY > Algorithm' 카테고리의 다른 글

[백준] 13549 숨바꼭질 3 python  (0) 2022.02.07
[백준] 2407 조합 python  (0) 2022.02.07
[백준] 14697 방배정하기 python  (0) 2022.02.06
[백준] 22942 데이터 체커 python  (0) 2022.02.05
[백준] 11365 !밀비 급일, C/C++  (0) 2022.02.04