백준 16563 <어려운 소인수분해> Python

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

---

소수 문제입니다.

단순히 하나하나 구하기에는 시간초과가 발생하므로 다른 방법을 찾아야 합니다.

 

소인수분해 문제는 어떤 수 K 를 소수 P 로 나누는 것을 반복합니다.

 

예를 들어

210 = 2 x (105)

       = 2 x 3 x (35)

       = 2 x 3 x 5 x 7

으로 순차적으로 구할 수 있습니다.

 

이는 큰 과정을 작은 과정으로 나누어 구할 수 있다는 말이고 DP 를 사용할 수 있는 조건임을 말합니다.

 

우선 나누어줄 인자인 소수를 구해줍니다.

범위는 주어진 수들 중 가장 큰 수의 제곱근 이하면 됩니다.

해당 범위의 소수들로 나누어 떨어지지 않는다면 그 수는 소수이기 때문에 따로 처리해주면 됩니다.

 

구해진 소수를 순회하며 인수분해 하고자 하는 수 K 를 나눠줍니다.

나누어 떨어질 경우 메모에 해당 소수를 기록해주고 몫의 소인수가 기록되어 있다면 이 또한 기록해줍니다.

몫의 소인수가 기록되어있지 않다면 재귀하며 다른 소수로 나누어줌을 반복합니다.

 

큰 수부터 진행하면 많은 인수를 포함할 확률이 높으므로 뒤에 올 수의 인수분해에 도움을 줄 수 있기 때문에 큰 수부터 진행할 수 있게 정렬해 진행했습니다. 

---

import sys

input = sys.stdin.readline


# 소인수 분해
def make_prime_factors(k, memo, primes):
    # k 의 소인수가 기록되어 있다면
    if memo[k]:
        # 소인수 리턴
        return memo[k]
    
    # 소수 순회
    for p in range(len(primes)):
        # 소수
        prime = primes[p]
        # 소수로 나누어떨어지면
        if not k%prime:
            # 기록
            memo[k].append(prime)
            # 재귀
            memo[k].extend(make_prime_factors(k//prime, memo, primes))
            # 리턴
            return memo[k]

        # 모든 소수로 나누어 떨어지지 않으면 자신이 소수
        elif p == len(primes)-1:
            # 기록
            memo[k].append(k)
            # 리턴
            return memo[k]


def solution(N, ks):
    # 수 내림차순 정렬
    sorted_ks = sorted(ks, reverse=True)
    max_ks = sorted_ks[0]
    # 소수 판정 리스트
    is_prime = [1 for _ in range(int(pow(max_ks, 1/2))+1)]
    is_prime[0] = 0
    is_prime[1] = 0
    # 소수 리스트
    primes = []
    # DP
    memo = [[] for _ in range(max_ks + 1)]
    # 순회
    for num in range(2, len(is_prime)):
        # 소수면
        if is_prime[num]:
            # 배수 모두 비소수 체크
            for non_prime in range(num*2, len(is_prime), num):
                is_prime[non_prime] = 0
            
            # 소수 리스트 추가
            primes.append(num)
            memo[num].append(num)
    
    # 순회하며 탐색 및 기록
    for k in sorted_ks:
        make_prime_factors(k, memo, primes)

    # 출력
    for k in ks:
        print(*sorted(memo[k]))


# 입력
N = int(input().strip())
ks = list(map(int, input().strip().split()))

solution(N, ks)