백준 1816 암호키 파이썬 문제풀이 [python 완전탐색]

백준 1816 문제 보러가기

 

백준 1816 암호키

n = int(input())
for i in range(n):
    s = int(input())

    if s <= 1000000:
        print("NO")
        break

먼저 입력을 받고 크기 확인부터 하자.

 

몇 년만의 알고리즘이라 소수 판별법을 까먹었다. 

대표적인 에라토스테네스의 체 방법은 너무 큰 숫자에서는 시간낭비이다.

 

일단 input 숫자의 범위는 \(10^{12}\)에서 \(10^{18}\) 까지이다.

시간을 생각해보면 에라토스테네스의 체는 O(n log(log n))으로 어려울 것 같다는 생각이 드는데..

 

소수는 결국 어떤로 나누어지는지 확인을 해야하고 아무리 확인해도 제곱근보다 큰 경우까지 볼 필요는 없다.

즉 범위가 \(10^{18}\)이면 확인해야하는 숫자는 \(10^9\) 까지.

 

1,000,000,000 이라는 것. 딱 10억이자 1초이다. 

10억개의 수까지 하나씩 증가하면서 나누어지지 않는지 확인해보면 소수가 아님을 판별할 수 있다는 뜻이다.

 

이렇게 백준에서 제한범위는 은근 힌트가 된다.

 

그럼 단순하게 생각하면 10억까지 1증 증가하면서 입력 숫자 S에 나누어보면 확인 가능하다.

연산을 더 줄이는 방법은 이 10억까지의 숫자 중 소수들만을 걸러낸 다음 확인하면 되는데, 

이 문제에서는 굳이 그럴 필요는 없을 것 같다. 

 

n = int(input())
for i in range(n):
    s = int(input())

    if s <= 1000000:
        print("NO")
        break

    isPrime = True

    for j in range(2,1000000000 + 1):
        if s % j == 0:
            isPrime = False
            print(j)
            break
    if(isPrime):
        print("YES")
    else:
        print("NO")

이 상태에서 검증하려고 

1000036000099

을 입력했는데 YES가 나와야하는데 NO가 나오길래 문제를 다시 읽었다.

 

어떤 수 S가 주어지면,
이 수가 우리가 생각하는 스케일이 작은 경우에서
적절한 암호 키인지 아닌지를 구하는 프로그램을 작성하시오.

만일 S의 모든 소인수가 \(10^6\) 보다 크다면
그 수는 적절한 암호 키이고,
그렇지 않은 경우는 적절하지 못한 암호 키가 된다.

그렇다. 이 조건을 안보고 풀려고 했다.

문제를 잘 읽는 것도 정말 중요하다.

 

아.. 소수를 찾는 문제가 아니구나

모든 소인수가 \(10^6\)보다 크다

라는 조건은 소인수가 없는 소수라면 만족하는 조건인가?

일단 명제의 관점으로 보면 그런 것 같다. 소수는 소인수가 자기 자신인데 그럼 \(10^6\) 의 조건을 충분히 만족할 것이다. 

 

n = int(input())
for i in range(n):
    s = int(input())

    if s <= 1000000:
        print("NO")
        break

    isPrime = True
    smallestFactor = 0

    for j in range(2,1000000000 + 1):
        if s % j == 0:
            isPrime = False
            smallestFactor = j
            break
    if isPrime or smallestFactor > 1000000:
        print("YES")
    else:
        print("NO")

이러한 조건으로 완성해서 제출해보았다.

 

실패..

 

시간 초과라고?  문제의 시간 제한은 2초로 되어있다.

아무래도 for문에서 \(10^{9}\) 까지 반복한게 문제인 것 같다. 

이미 1,000,000,000 로 1초인데, 두 번만 반복해도 2초가 넘는다.

 

문제에서는 소인수가 \(10^6\)만 넘으면 된다고 했다. 

그럼 거기까지 확인하고 그 위의 수들은 확인안해도 없다면 소수이고, 있다면 이미 \(10^6\) 을 넘었으니 

확인할 필요가 없는 값들이다.

 

n = int(input())
for i in range(n):
    s = int(input())

    if s <= 1000000:
        print("NO")
        break

    isPrime = True
    smallestFactor = 0

    for j in range(2,1000000 + 1):
        if s % j == 0:
            isPrime = False
            smallestFactor = j
            break
    if isPrime or smallestFactor > 1000000:
        print("YES")
    else:
        print("NO")

반복문을  \(10^6\) 까지만 반복해주자. 

 

해결