문제
https://www.acmicpc.net/problem/22943
접근
- 문제에서 어떤 k와 m이 주어지든지 간에 소수, 소수의 합으로 만들 수 있는 수, 소수의 곱으로 만들 수 있는 수는 정해져 있으므로 에라토스테네스의 체를 이용하여 소수를 구한다.
- 구해진 소수들을 이용해서 덧셈과 곱셈으로 만들 수 있는 수들을 미리 구해놓고 백트래킹으로 해당 수가 조건을 만족하는지 확인했다.
풀이
def solve(num):
global ans
if len(num) == k:
num = int(num)
if add[num]:
while num % m == 0:
num //= m
if mul[num]:
ans += 1
return
for i in range(10):
if not check[i]:
check[i] = True
solve(num + str(i))
check[i] = False
# 에라토스테네스의 체
prime = [True] * (10 ** 6)
prime[0] = prime[1] = False
for i in range(2, 10 ** 6):
if prime[i]:
for j in range(2 * i, 10 ** 6, i):
prime[j] = False
k, m = map(int, input().split())
# 덧셈
add = [False] * (10 ** k)
for i in range(2, 10 ** k):
if prime[i]:
for j in range(i, 10 ** k):
if not prime[j] or i == j:
continue
if i + j >= 10 ** k:
break
add[i + j] = True
# 곱셈
mul = [False] * (10 ** k)
for i in range(2, 10 ** k):
if prime[i]:
for j in range(2, 10 ** k):
if not prime[j]:
continue
if i * j >= 10 ** k:
break
mul[i * j] = True
# 만들 수 있는 모든 숫자에 대해 확인
check = [False] * 10
ans = 0
for i in range(1, 10):
check[i] = True
solve(str(i))
check[i] = False
print(ans)
'Python > Coding Test' 카테고리의 다른 글
21940 가운데에서 만나기 (0) | 2022.03.07 |
---|---|
19844 단어 개수 세기 (0) | 2022.03.07 |
4803 트리 (0) | 2022.03.01 |
19641 중첩 집합 모델 (0) | 2022.02.28 |
22871 징검다리 건너기 (large) (0) | 2022.02.27 |