[BOJ] 백준 16400번 소수 화폐 - 파이썬(Python)

문제

소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다.

소수나라에 놀러 온 하나는 관광을 하다가 가격이 N인 물건을 발견하고 너무 마음에 들어 999983원을 내고 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다.

물건을 구매하려던 하나는 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수가 얼마나 되는지 궁금해졌다.

하나를 도와 N원을 지불하기 위한 가짓수가 얼마나 되는지 구해보자.

단, 하나는 소수나라의 모든 화폐가 무한정 있다고 가정한다.

입력

구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다.

출력

소수나라의 화폐를 이용하여 지불할 수 있는 방법의 수를 출력한다.

단, 지불할 수 있는 방법의 수가 매우 크기때문에, 123,456,789로 나눈 나머지 값을 출력한다.

 

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

16400번: 소수 화폐

 

💡 풀이 및 코드

import math

def is_prime(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

n = int(input())
prime = []

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

dp = [0 for _ in range(n+1)]
dp[0] = 1
for p in prime:
    for i in range(p, n+1):
        dp[i] = (dp[i] + dp[i-p]) % 123456789
            
print(dp[n])

백준 2293번 문제와 비슷한 유형의 DP 문제이다. 아이디어가 헷갈린다면 아래 게시물을 참고하자.

( 참고: https://zu-techlog.tistory.com/48?category=948141 )

[BOJ] 백준 2293번 동전1 - 파이썬(Python)

입력받은 수 n보다 작은 소수 집합을 구하는 과정에서 실행 시간 단축하는 것이 관건이었다. 기존의 방식으로 is_prime 함수에서 소수를 판별할 때 반복문을 2부터 판별할 수(num)까지 돌아가게 한다면 시간복잡도가 O(n^2)가 되어 시간초과가 난다. 따라서, is_prime 함수 내에서 반복문을 약수의 특성을 반영해 num까지가 아닌 num의 제곱근 값까지만 돌려 소수를 판별했다. 이로써 시간초과 문제가 해결되었다. 하지만 아쉽게도 백준 정답 제출 시 언어를 Python3로 설정하면 여전히 시간초과가 발생했다. PyPy3로 제출해야만 정답으로 인정되었다. 아직 Python3로 통과할 수 있는 방법은 찾지 못했으며, 파이썬으로 문제를 맞춘 다른 이용자들도 모두 PyPy3로만 제출한 것으로 보아 해당 알고리즘이 최선인 것 같다.