[Python] 백준 2061번 - 좋은 암호 / 백준 1837 - 암호제작

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

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

---

2061을 푼 후 문제를 찾다가 알게됐는데 2061이랑 1837은 문제가 거의 같아서 같은 코드로 둘 다 풀 수 있었다.

 

문제(2061)

암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.

소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K와 정수 L이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 할 때 1로 나누는 경우는 고려하지 않는다.

예를 들어 K=143인 경우, 이는 11과 13의 곱으로 이루어져 있다. 즉, 이를 인수분해 하는 방법은 11×13, 143의 두 가지 경우뿐이다. 따라서 L이 11일 경우에는 인수분해 했을 때 나온 수들이 모두 L 이상이므로 좋은 경우지만, L이 12이상일 경우에는 좋은 암호가 아니다.

K와 L이 주어졌을 때, 좋은 암호인지 판단하는 프로그램을 작성하시오.

 

처음 짠 코드

K, L = map(int, input().split())
nums = []

for i in range(2, int(K ** 0.5)+1):
    if K%i == 0:
        nums.append(i)

min = min(nums)

if min >= L:
    print("GOOD")
else:
    print("BAD", min)

문제를 보고 생각난대로 바로 코드를 작성해서 제출했는데 시간 초과가 떴다. 아무래도 큰 숫자를 돌리나보다... 싶어서 코드를 다시 짰다.

 

시간 초과를 맛보고 개선한 코드

K, L = map(int, input().split())

prime = [True] * L
prime[0] = prime[1] = False

for i in range(2, int(L ** 0.5)+1):
    if prime[i]:
        for j in range(i*i, L, i):
            prime[j] = False

for i in range(2, L):
    if prime[i] and K % i == 0:
        print("BAD", i)
        break
else:
    print("GOOD")

이번 코드는 에라토스테네스의 체를 사용했다. 전에 다른 문제에서도 사용해봤어서 기억에 남아있는 알고리즘이다.

에라토스테네스의 체를 간단하게 설명하자면 2를 제외한 2의 배수를 제거하고 3을 제외한 3의 배수를 제거한다. 이런 식으로 소수의 배수들을 지워 간단하고 빠르게 소수를 찾아내는 방법이다. 

 

풀이

이 코드는 처음 짠 코드와 달리 K의 모든 소인수를 찾지 않는다. L보다 작은 K의 소인수만 찾는다.

 

1. 먼저 K와 L을 받아준다.

2. L의 길이만큼 리스트를 만들고 모두 True로 설정한다.

    2-1. L이 3이라면 [True, True, True] 이렇게 생성된다.

3. 0과 1은 소수가 아니기에 제외한다.

4. 첫 번째 for문에서 에라토스테네스의 체를 사용하여 L보다 작은 소수를 찾는다.

    4-1. prime[i]가 True일 때, 중첩for문에서 i의 배수(j)를 False로 바꾼다.

5. 두 번째 for문에서 L보다 작은 소수 중에 K의 소인수가 있는지 찾아보고 있다면 BAD와 그 값을, 그리고 아니라면(else) GOOD을 출력한다.