[백준-Python] 좋은암호 : 2061번

🥉 Bronze3

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

 

❎ 1차 풀이

import math
import sys
from itertools import permutations

# 두 소수 구하기
# 두 소수가 l 이상인지 확인
# O - good
# X - 더 작은 소수 출력

input = sys.stdin.readline
k, l = map(int, input().rstrip().split())

for divisor in range(l,k): 
    # 두 소수 찾기
    if k%divisor==0:
        num2=k//divisor
        num1=divisor

        if num2<l or num1<l:
            print('BAD',min(num1,num2))
            break
        else:
            print('GOOD')
            break

처음에 생각했던 방식은 주어진 k=143를 소인수분해 했을때 추출되는 두 값이 모두 l이상이라면 GOOD, 아니라면, BAD를 출력하면 되기 때문에 l부터 나눠지는수를 찾아, 소인수분해가 가능하면 나눈 값 divisor와 몫이 찾고자하는 두 소수가 될것이고, 두 수가 중 하나라도 l값보다 작다면 BAD와 num1(더 작은값)을 출력하는 방식으로 풀었지만, 역시나 다음과 같이 어마어마한 범위이기 때문에 1씩 증가하며 찾는 이 방식은 시간초과가 발생하였다...

 

✅ 정답 풀이

import sys

# 소수
# l보다 작은 값으로 나눠지면, bad

input = sys.stdin.readline
k, l = map(int, input().rstrip().split())


for divisor in range(2,l):
    if k%divisor==0:
        print('BAD',divisor)
        break
else:
    print('GOOD')

메모리	시간
31120KB	280ms

 

l이상의 소인수분해를 찾아서, 두 값 모두 l이상인지 확인하는것이 아닌 반대로 생각해서

찾고자하는 두수는 어차피 소수이기 때문에, 2부터 l까지 나눠진다면 좋은 암호의 조건이 위배되는것이다.

K는 10^100, L은 10^6이기 때문에 더 작은수로 인수분해가 가능한지를 확인하는것이 훨씬 효율적인 방법이다!

 

✅ 다른 풀이

def find_prime_numbers(n):
    isPrimes=[True]*(n+1)
    p=2 #소수 검사 시작할 숫자

    while(p*p<=n):
        if isPrimes[p]==True:
            for i in range(p*p,n+1,p): #p의 배수들을 false로 설정 (p제곱부터 n까지)
                isPrimes=False
        p+=1 #다음수로 이동
    prime_numbers = []

    # 2-n까지 소수인수를 prime_numbers 리스트에 저장
    for p in range(2,n+1):
        if isPrimes[p]:
            prime_numbers.append(p)
    return prime_numbers



def check_good_password(K, L):
    primes = find_prime_numbers(L - 1)
    
    for prime in primes:
        if K % prime == 0:
            return f"BAD {prime}"
    
    return "GOOD"

K, L = map(int, input().strip().split())
print(check_good_password(K, L))

 

 

처음에 풀었던 풀이가 시간초과가 발생하는 것을 보고, for문으로 1씩 증가시키면서, 무작정 찾는것이 아니라 어차피 소수이므로 소수 리스트를 만들어서 그중에서 찾아야되나 생각을 했는데 이럴때 에라토스네스체를 사용하는데... 예전에 어려움을 느꼈던 알고리즘이라 패스했는데 다른 팀원이 이 정석대로 풀이를 했길래 가져와보았다!

 

 

 

 

에라토스네스 체

소수를 판별하는 알고리즘으로, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간복잡도로 빠르게 구할 수 있다고한다.

 

1. 2부터 시작해서 특정수의 배수에 해당하는 모든 수를 지운다.

2. 2부터 시작해 남아있는 모든 수를 출력한다.

 

 

 

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[Algorithm] 에라토스테네스의 체