취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2023번 문제인 신기한 소수이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2023 

왼쪽서부터 읽은 1, 2, ... N자리 수가 모두 소수인 N자리 수를 모두 찾는 문제이다. 메모리 제한이 매우 작아, 에라토스테네스의 체 등을 사용하기 어렵다는 점을 확인하자.

K자리 수까지 모두 소수인 수를 찾고, 이 수에 숫자를 하나 이어붙여서 그 수 또한 소수가 된다면 K+1자리까지 소수인 수를 찾을 수 있다. 이러한 과정으로 백트래킹을 통해 문제를 해결해보자.

이러한 수가 매우 적다는 것은 구현을 통해 직접 확인해볼 수 있다. 이러한 수가 매우 적으므로, 백트래킹을 이용한 풀이 코드는 제한시간 내에 충분히 빠르게 돌아간다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
void func(int K, int digit) {
	for (int i = 2; i * i <= K; i++) {
		if (K % i == 0) return;
	}
	if (digit == N) cout << K << '\n';
	else {
		for (int i = 0; i < 10; i++) {
			func(K * 10 + i, digit + 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	func(2, 1);
	func(3, 1);
	func(5, 1);
	func(7, 1);
}