[백준/파이썬] 1837번: 암호제작

👩🏻‍💻 문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

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

1837번: 암호제작

 

• 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키
• 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기
• 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성

 

+) 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것. . . 이 문제는 브루트 포스?

 

👩🏻‍💻 입력

암호 P(4 ≤ P ≤ 10^100)와 K (2 ≤ K ≤ 10^6) 이 주어진다.

 

 

👩🏻‍💻 출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

 

👩🏻‍💻 예제

---

👩🏻‍💻 코드

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

for i in range(2, K):
    if P % i == 0:
        print("BAD", i)
        break
else:
    print("GOOD")

 

→ 입력으로 두 정수 P와 K를 받고, P가 2부터 K-1까지의 어떤 정수로도 나누어떨어지지 않는 경우 "GOOD"을 출력, 그렇지 않으면 P를 나누는 첫 번째 정수를 "BAD"와 함께 출력하는 코드

 

# 입력
P, K = map(int, input().split())

1. input() 함수로부터 받은 입력 문자열을 공백을 기준으로 분리합니다. split() 함수는 문자열을 분리한 후 리스트로 반환합니다.
2. map(int, ...)를 사용하여 분리된 두 문자열을 정수로 변환합니다. 이렇게 하면 두 정수가 변수 P와 K에 각각 할당됩니다.

ex. 사용자가 "10 5"라는 입력을 제공한다고 가정하면,

1. input() 함수는 "10 5" 문자열을 받습니다.
2. split() 함수는 이 문자열을 공백을 기준으로 분리하여 ["10", "5"]라는 리스트를 생성합니다.
3. map(int, ...)를 사용하여 각각의 문자열을 정수로 변환하여 P에는 10이, K에는 5가 할당됩니다.

 

for i in range(2, K):
    if P % i == 0:
        print("BAD", i)
        break
else:
    print("GOOD")

 

for 루프를 사용하여 i를 2부터 K-1까지의 정수로 반복합니다.

1. 각 i에 대해서, P를 i로 나눴을 때 나머지를 검사합니다. P % i가 0이면 P가 i로 나누어떨어진다는 의미이므로 "BAD"와 i의 값을 출력하고 루프를 종료합니다. 이 때 break 문이 사용되어 루프를 종료합니다.
2. 만약 break 문이 실행되지 않고 for 루프가 정상적으로 종료된다면, K까지 나눠지는 어떤 정수도 발견되지 않았으므로 "GOOD"을 출력합니다.

 

ex. 사용자가 "10 5"를 입력한 경우,

1. P에 10, K에 5가 할당됩니다.
2. for 루프가 2부터 4까지 i를 반복합니다.
3. i가 2일 때, 10을 2로 나누면 나머지가 0이므로 "BAD 2"를 출력하고 루프를 종료합니다.

---

👩🏻‍💻 정답 제출