[백준] 22943_수 / python

https://www.acmicpc.net/problem/22943https://www.acmicpc.net/problem/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은 정수

---

여기서 소수가 정말 많이 쓰이는데, 일단 정말 소수가 많이 쓰이므로 나는 에라토스테네스의 체로 소수 리스트를 만들어 두고, 거기서 소수가 있는지 체크를 하는 방식으로 알고리즘을 구현했다.

 

 

 

- 그리고, 소수 리스트를 만들 때 set 자료형으로 구현해 소수 리스트 안에 있는지 판단하는 연산에 걸리는 시간 복잡도를 줄였다.

 

- itertools의 permutations을 사용하여 조합을 구현했으며, 첫 자리가 0인 경우는 continue문을 사용해 걸러 주었다.

 

- 또한, 조건2를 먼저 체크하고 조건 1을 확인하는 식으로 했는데, 이는 조건 2를 체크할 때 m으로 나누어 연산을 진행하므로 아무래도 수를 조금이나마 크기를 줄여 확인해 더 확인하기 쉽게 했고, 조건 1에서 소수의 합이 되는 경우를 찾는 것보다 소수인 약수를 구하는 게 소수 리스트를 활용하여 할 수 있어서 더 빠르게 구현이 가능했기 때문이다.

 

코드는 다음과 같다.

from itertools import permutations
k, m = map(int, input().split())
lst = []
MAX = 98765 // 10**(5-k)    # K개의 숫자를 고를 때 나올 수 있는 가장 큰 수

# 일단 최대 범위까지 소수 리스트 만들어 놓음
check = [0] * (MAX + 1)
prime_lst = set()   # 있는지 체크하기에는 set 자료형이 최고
for i in range(2, MAX+1):
    if check[i] == 0:
        check[i] = 1
        prime_lst.add(i)  # 1부터 N까지 소수 리스트
        j = 1
        while i * j <= MAX:
            check[i*j] = 1
            j+=1

# k개의 숫자 조합
for num in permutations(range(10), k):
    if num[0] == 0: # 첫 자리가 0이면 취급 안함
        continue
    N = int(''.join(list(map(str, num))))   # 숫자 조합
    temp = N
    while temp % m == 0:    # m으로 나누어떨어지지 않을 때까지 나눠줌
        temp //= m
    i = 2
    temp_lst = []
    while i <= int(temp**0.5):  
        if temp % i == 0:   # 한 번이라도 소수와 소수가 아닌 수가 있어도 반례이므로 break 해줌
            if i in prime_lst and temp//i in prime_lst: # 2조건
                j = 2
                while j < N // 2:  # 1조건
                    if j in prime_lst and N-j in prime_lst:
                        lst.append(N)
                        break
                    j += 1
            break   #?
        i += 1
                    
print(len(lst))

 

처음에는 단지 리스트로 구현을 했다 시간이 너무 오래 걸려 한번 조건 부분을 손보고 리스트로 set으로 바꾸니 훨씬 연산이 빨라졌다.

시간 복잡도 개선을 위해서 set이나 deque자료형을 쓰는 것을 아끼지 말아야겠다.