[백준 22943번] 파이썬 - 수

백준 22943 - 수

시간 제한 2초, 메모리 제한 1024MB

# 조건

• 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은 정수

# 접근 방법

• 처음에 접근을 잘못하여 python으로 ac받기에 시간이 조금 걸린 문제이다.
• k=5이며 0부터 9까지 한 번씩만 사용하므로 최대로 뽑을 수 있는 수는 98765 // 10 ** (5-K)이다.
  • 위의 수를 max_val로 저장
• 따라서 에라토스테네스의 체를 이용하여 max_val 이하의 소수들을 판별해주며 소수인 경우 nums 리스트에 따로 저장해준다.
  • 2부터 시작할 때 이미 배수들은 False로 변경되었으므로 반복문 시작시 True인 경우 소수이다.
• 여기서 생각을 잘못한 부분이 K가지의 숫자로 만들 수 있는 수들을 2가지 조건에 의하여 판별을 해주는데

# nums = 판별된 숫자를 모아둔 리스트
for i in range(leng):  
    for j in range(i, leng):  
        if i != j and nums[i] + nums[j] <= max_val:  
            sum_value.add(nums[i] + nums[j])  

        if nums[i] * nums[j] <= max_val:  
            multiply.append(nums[i] * nums[j])

• 2번 조건의 M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우 만족하는 것을
  • K가지의 숫자로 만든 수가 아닌 나누어 떨어지지 않을때까지 나눠진 수로 기록해주었기 때문이다.
  • 따라서, 나누어 떨어지지 않는 수가 소수 쌍의 곱에 존재한다면, 원본 val을 +=1을 해주었다.

for k in permutations(range(10), K):  
    if k[0] == 0:  
        continue  
    # 숫자로 만들어주기  
    val = int(''.join(list(map(str, k))))  
    t = val  
    # 조건 1 만족하는 수  
    if val in sum_value:  
        temp[val] += 1  
    # 조건 2 만족하는 수  
    while t % M == 0:  
        t //= M  
    if t in multiply:  
        temp[val] += 1

# pypy 통과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import permutations  
from collections import defaultdict  

K, M = map(int, input().split())  
nums = []  
# K자리 숫자로 만들수 있는 최대 값  
max_val = 98765 // 10**(5-K)  
decimal = [True] * (max_val+1)  
decimal[0] = False  
decimal[1] = False  
for i in range(2, max_val):  
    if decimal[i]:  
        nums.append(i)  
    j = 2  
    while i*j <= max_val:  
        decimal[i*j] = False  
        j += 1  
leng = len(nums)  
sum_value = set()  
multiply = []  

for i in range(leng):  
    for j in range(i, leng):  
        if i != j and nums[i] + nums[j] <= max_val:  
            sum_value.add(nums[i] + nums[j])  

        if nums[i] * nums[j] <= max_val:  
            multiply.append(nums[i] * nums[j])  


temp = defaultdict(int)  
for k in permutations(range(10), K):  
    if k[0] == 0:  
        continue  
    # 숫자로 만들어주기  
    val = int(''.join(list(map(str, k))))  
    t = val  
    # 조건 1 만족하는 수  
    if val in sum_value:  
        temp[val] += 1  
    # 조건 2 만족하는 수  
    while t % M == 0:  
        t //= M  
    if t in multiply:  
        temp[val] += 1  

result = 0  
r = []  
for i, j in temp.items():  
    if j >= 2:  
        result += 1  
        r.append(i)  
print(result)

# python 통과

• 위의 로직에서 시간을 줄여주기 위하여 소수들의 덧셈과 곱셈을 구하는 부분을 나누었다.
  • 덧셈과 곱셈을 같이 구하니 break 할 타이밍을 놓쳐 시간이 비효율적으로 사용된다고 판단하였기 때문에!!
• 또한, dictionary에 저장해서 2 이상인 => 2 조건을 모두 만족하는 수들의 갯수를 찾는 것이 아닌
  • 조건 1을 통과하고 조건 2를 통과한 수에 대해 바로 result += 1을 해주었다.
• set와 list 안에서 값을 찾는 것도 시간 차이가 많이 나기 때문에, 문제에 따라 set를 사용할 수 있다면 활용해주자!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import permutations  

K, M = map(int, input().split())  
nums = []  
# K자리 숫자로 만들수 있는 최대 값  
max_val = 98765 // 10 ** (5 - K)  
decimal = [True] * (max_val + 1)  
decimal[0] = False  
decimal[1] = False  
for i in range(2, max_val):  
    if decimal[i]:  
        nums.append(i)  
    j = 2  
    while i * j <= max_val:  
        decimal[i * j] = False  
        j += 1  
leng = len(nums)  
sum_value = set()  
multiply = set()  

# 덧셈 구해주기  
for i in range(leng-1):  
    for j in range(i+1, leng):  
        if nums[i] + nums[j] > max_val:  
            break  
        sum_value.add(nums[i] + nums[j])  

        # 곱셈 구해주기  
for i in range(leng):  
    for j in range(i, leng):  
        if nums[i] * nums[j] > max_val:  
            break  
        multiply.add(nums[i] * nums[j])  

result = 0  
for k in permutations(range(10), K):  
    if k[0] == 0:  
        continue  
        # 숫자로 만들어주기  
    val = int(''.join(list(map(str, k))))  
    t = val  
    # 조건 1 만족하는 수  
    if val in sum_value:  
        # 조건 2 만족하는 수  
        while t % M == 0:  
            t //= M  
        if t in multiply:  
            result += 1  
print(result)