[Python/파이썬] 백준 22943번 수

22943번: 수

 

문제

0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다.

1. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
2.  $M$으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

예를 들어, $K$가 1이고 $M$이 11인 경우로 생각해보자. 한자리 수 중 1번 조건을 만족하는 수는 5, 7, 8, 9이고 2번 조건을 만족하는 수는 4, 6, 9가 있다. 이 두개의 조건을 둘다 만족하는 수는 9이므로 이 경우에는 1개이다.

입력

첫 번째 줄에 $K$와 $M$ 주어진다.

출력

2가지 조건을 만족하는 수의 개수를 출력한다.

 

제한

•  $1 ≤ K ≤ 5$ 
•  $2 ≤ M ≤ 10^9$ 
•  $K, M$은 정수

 

 

코드

from itertools import permutations
from math import sqrt

# 에라토스테네스의 체
prime = [True] * 98765
prime[0] = False
prime[1] = False
for i in range(2, int(sqrt(98765))+1):
    if prime[i]:
        for j in range(i*i, 98765, i):
            prime[j] = False


def chk(num, m):
    flag = False
    # 서로 다른 두 개의 소수의 합인 경우
    for i in range(2, num//2+1):
        if i != (num-i) and prime[i] and prime[num-i]:
            flag = True
            break
    if not flag:
        return False
    # M으로 나누어 떨어지지 않을 때까지 나눈 수가 두 개의 소수의 곱인 경우
    while num % m == 0:
        num //= m
    for i in range(2, int(sqrt(num))+1):
        if num % i == 0 and prime[i] and prime[num//i]:
            return True
    return False


k, m = map(int, input().split())
ans = 0
for p in permutations(range(0, 10), k):
    p = list(map(str, p))
    if p[0] == '0':
        continue
    num = int(''.join(p))
    if chk(num, m):
        ans += 1
print(ans)

 Python3로는 시간 초과가 발생해서 통과하지 못했고 PyPy3로는 통과했다.

문제 풀이 방법은 바로 알았지만 시간 초과를 해결하지 못해서 오래 걸렸는데 구글링해서 찾은 코드들도 Python3로는 통과 못하길래 그냥 PyPy3로는 통과하는 것에 만족하기로 했다....