BOJ 24039 - 2021은 무엇이 특별할까?

문제 링크

문제#

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

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

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

입력#

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

출력#

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

풀이#

문제의 특별한 수는 서로 이웃한 두 소수의 곱이다. 입력 범위가 작기 때문에 가능한 특별한 수들을 미리 계산해 두고, 그중 N보다 처음으로 큰 값을 고르면 된다.

현재 코드는 인접한 소수의 곱을 오름차순 배열로 보관한다. 이후 배열을 앞에서부터 훑으면서 N보다 큰 첫 값을 출력한다. 문제에서 필요한 것은 소수 목록 자체가 아니라 이미 만들어진 특별한 수의 순서이므로, 고정된 범위에서는 이 방식이 가장 단순하다.

코드#

#include <iostream>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int prime[26] = { 6, 15, 35, 77, 143, 221, 323, 437, 667, 899, 1147, 1517, 1763, 2021, 2491, 3127, 3599, 4087, 4757, 5183, 5767, 6557, 7387, 8633, 9797, 10403 };
 
	int N;
	cin >> N;
 
	for (int i = 0; i < 26; i++) {
		if (prime[i] > N) {
			cout << prime[i] << '\n';
			break;
		}
			
	}
 
	return 0;
 
}

복잡도#

• 시간 복잡도: 고정된 길이의 배열만 확인하므로 $O(1)$이다.
• 공간 복잡도: 고정된 특별한 수 목록만 사용하므로 $O(1)$이다.

마무리#

특별한 수의 후보가 작고 고정되어 있다는 점을 이용하면 계산보다 조회에 가깝게 풀 수 있다. 오름차순 목록에서 N보다 큰 첫 값만 찾으면 된다.