[Python/파이썬] 백준 16400번 소수 화폐

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

코드

n = int(input())


def prime_number(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False

    prime = []

    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
            prime.append(i)
    return prime


prime = prime_number(n)
dp = [0]*(n+1)
dp[0] = 1
for p in prime:
    for j in range(p, n+1):
        dp[j] = (dp[j] + dp[j-p]) % 123_456_789

print(dp[n])

 

에라토스테네스의 체를 이용하여 N 이하의 소수들을 구한 뒤, 이 소수들을 갖고 각 금액을 만들 수 있는 가짓수를 구하는 코드이다.

금액을 만들 수 있는 가짓수를 구하는 데에는 DP를 사용했다.

1. 크기가 N+1이고, 원소들은 모두 0인 dp 배열을 만든다. 이때 인덱스는 금액, 원소 값은 소수 동전을 사용하여 해당 금액을 만들 수 있는 가짓수이다.

2. 동전을 아무것도 사용하지 않았을 때 0원을 만들 수 있으므로 dp[0] = 1이다.

3. 소수 동전을 하나씩 추가한다고 생각하고 dp 배열의 값을 채워나간다. 예를 들어, 2원 동전을 추가했을 때, j라는 금액을 만들 수 있는 경우는 j-2원에 2원을 하나 더한 것과 같다. 그렇기 때문에 dp[j] = dp[j] + dp[j-p]가 되는 것이다.

 

그런데 이 코드는 PyPy3로는 통과하지만, Python3로는 시간 초과가 발생했다. 에라토스테네스의 체는 시간 복잡도가 O(n * log(log n))으로 효율적인 알고리즘인데도 시간 초과가 발생했다. Python3는 인터프리터 언어이기 때문에 처리 속도에 한계가 있기 때문인것 같다.

 

시간을 더 줄이기 위해 에라토스테네스의 체를 좀 더 최적화했다.

from math import sqrt

def prime_number(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    prime = []
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
    return prime

 

두 가지를 개선했다.

 

1. 제곱근까지만 반복하도록 변경: N의 제곱근보다 큰 소수 p에 대해서는, p^2가 이미 N을 초과하기 때문에 확인할 필요가 없다. 즉, N 이하의 모든 합성수는 N 제곱근 이하의 소수들의 배수로 표현될 수 있으므로, N의 제곱근까지만 검사하면 충분하다.

 

2. 내부 반복문의 시작점을 i*2에서 i*i로 변경: 소수 i의 배수 중 i*i보다 작은 수들(i*2, i*3, ..., i*(i-1))은 이미 더 작은 소수들의 배수로서 처리되었기 때문이다. 예를 들어, 소수 5의 경우 5*2=10, 5*3=15, 5*4=20은 이미 소수 2와 3의 배수로서 처리되었으므로, 5*5=25부터 시작하면 된다.

 

근데 이것도 Python3로는 여전히 시간 초과가 발생한다.

해결 방법을 아신다면....댓글 주세요