[파이썬 풀이] 24039번: 2021은 무엇이 특별할까? - 백준

백준 24039번:  2021은 무엇이 특별할까?

알고리즘 분류: 수학, 정수론, 소수 판정

파이썬(Python) 풀이

 

링크: https://www.acmicpc.net/problem/24039

문제

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

 

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

 

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 주어진 수 N 이 주어진다.

---

출력

첫 번째 줄에 N 보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

---

풀이

이 문제의 핵심은 N의 값이 1 이상 10,000 이하를 이용하는 것이다.

 

먼저 N의 값이 10,000 이하 이므로, 두 소수의 곱은 최대 10X * 10X정도라고 생각할 수 있다.

 

따라서 2부터 3, 5, 7..., 100 언저리정도의 소수까지 미리 리스트를 만들어 두고 일일이 비교하면 된다.

 

그러면 다음과 같이 코드를 작성하게 된다.

 

S라는 리스트를 만들고, num라는 변수를 만들어서 120이하의 소수를 리스트에 담는다.

그리고 N이라는 값을 입력받으면 리스트의 [0]과 [1]의 곱, [1]과 [2]의 곱, ... 이런식으로 비교를 하면 된다.

 

---

다음은 재미로 보세요!

이번에 소개할 것은 숏코딩이다.

밑에 사진을 보면 전체 2등임을 알 수 있다!(나름 숏코딩 등수에 맞추는것도 즐겁다)

 

숏코딩 2등

이 방법은 앞에 소개한 것과 비슷한데 리스트를 코드로가 아닌 미리 만들어 두는 것이다.

 

따라서 소수를 2부터 3, 5, 7, 11, ... , 101, 103까지 리스트에 미리 담아둔다.

그리고 조건이 N >= S[i]*S[i+1]인 반복문을 통해 계속해서 큰 값이 나올때까지 구하면 된다.

 

하지만 소수를 일일이 적는것은 쉽지 않다는 것을 누구나 다 알 것이다.

그리고 101과 103이 소수인것을 외우고 있는 사람은 그리 많지 않다.

따라서 좋은 코드라고는 못한다. 어디까지나 숏코딩은 "재미"라고 생각한다.

이해하기 쉬운 코드가 매우 좋은 코드라고 생각하기 때문이다 :)