[Python] 백준 20302 민트초코

문제 링크 : https://www.acmicpc.net/problem/20302

20302번: 민트 초코

1. 접근 방법

간단한 소수 찾기 + 소인수 분해 문제라고 생각했다.

과정에서 많은 시간 초과가 났고, 그 이유를 잘 떠올리지 못했는데, 소수 판정에서 가장 간단할 수 있는 부분에서 많은 실수를 했다.

 

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/20000/20302.py

GitHub - mintropy/baekjoon_py

📕코드 해설

우선, 모든 소수에 대하여 확인할 필요가 없다.

자연수 N에 대하여, N이 소수인지 판별하기 위해서는 N ^ 1/2 까지만 확인하면 된다. 이 부분에서 전체 탐색을 하며 시간 초과가 났다고 생각한다.

따라서 이 문제에서 최대 100,000까지 확인하기 위해 확인해야 할 최대 소수는 350쯤 이였던 것으로 기억한다.

그래서 만약 합성수이면  모두 나누어주며 계산하고, 모든 소수를 확인해도 소수를 찾지 못하면 이보다 더 큰 소수임을 확인 할 수 있다.

 

풀이 과정을 조금 더 넓게 풀어쓰면 다음과 같다.

모든 숫자는 분자 또는 분모로 사용되게 되고, 각각의 숫자에 해당하는 소인수분해 값이 존재하는데, 해당 소인수분해에서 소수의 몇 제곱인지를 분자이면 더하고, 분모이면 빼주는 방식으로 가능한지 확인했다.

만약 어떤 소수가 분자에서 나타나는 총 횟수가 분모에서 나타는 횟수보다 많다면 정수가 될 수 있고, 아니라면 불가능하다. 이를 모든 소수로 확장하여 주어진 식이 정수가 될 수 있는지 판별한다

 

 

3. 생각 정리

소수 판별은 어렵지 않지만, 항상 모든 소수를 찾고, 확인할 필요가 없다는 것을 종종 망각하는 것 같다.

이번 문제에서 큰 차이가 아니라고 느낄지라도, 엄청나게 큰 차이를 만들어 내기도 한다.