💡문제접근
- 이 문제의 위에 나와있는 소스코드의 의미를 해석하는 부분에서 많은 시간이 걸렸다. 소스코드를 보면서 어떤 것을 구해야하는지 알아냈고 이 문제의 의미는 다음과 같다.
"N의 약수(단, N은 제외) 중에서 가장 큰 약수를 구하려면 몇 번 감소시켜야 하는가?"
- N의 값의 범위는 1 ≤ N ≤ 10^9으로 1씩 감소시켜서 나간다면 당연히 시간초과가 발생할 것이다.
- N의 약수를 구할 때는 1부터 N의 제곱근까지의 수만 0으로 나누어 떨어지는지 확인하면 된다. 다음 예시를 통해서 이해해보자.
ex. 100의 약수를 구하는 과정
100 % 1 = 0
100 % 2 = 0
100 % 3 = 1
100 % 4 = 0
100 % 5 = 0
100 % 6 = 4
100 % 7 = 2
100 % 8 = 4
100 % 9 = 1
100 % 10 = 0
- 이를 통해서 100의 약수는 일단 1, 2, 4, 5, 10을 갖는다는 사실을 알게 되었다. 이제 이 구해진 수들을 이용해서 다른 약수들을 찾아보자.
- 100에 위의 구해진 수들을 나누는 것이다.
100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10
- 그렇게 되면 이미 구했던 1, 2, 4, 5, 10, 20, 25, 50, 100이 나오게 되고 100의 약수를 모두 구할 수 있게 된다.
💡코드(메모리 : 31256KB, 시간 : 44ms)
import sys
input = sys.stdin.readline
N = int(input())
i = 2
Counter = 1
while i * i <= N:
if N % i == 0:
Counter = N // i
break
i += 1
print(N-Counter)💡소요시간 : 27m
🐢