제3회 흐즈로컵 (The 3rd Chromate Cup) Algorithm Division

대회 날짜 : 2024년 1월 7일

난이도 : Bronze ~ Ruby (Codeforces 기준 *800 ~ *3000)

문제 수 : 11문제

등수 : 147/181

 

이번 백준의 대회는 전체적으로 나에게 어려웠다.

대회가 8시에 시작했는데 나는 기숙사 입사 때문에 8시 30분쯤에 시작했다.

나는 이 대회를 하면서 그냥 뱃지를 얻는 것이 목표여서 내가 좋아하는 소수분야인 2번 문제만 선택했다.

 

BOJ 31216번. 슈퍼 소수

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

소수는 수학을 사랑하는 누구에게나 매우 중요한 개념입니다. 1보다 크면서 약수가 1과 자기 자신 뿐인 자연수를 소수라고 부릅니다. 흐즈로는 소수 중에서도 더욱 특별한 소수가 있다고 생각했습니다. 다음을 만족하는 소수 P를 슈퍼 소수라고 부릅니다. 소수 P가 모든 소수 중 K번째로 작은 소수라고 합시다. 이때 K가 소수임을 만족합니다. 정수 N이 주어질 때, 모든 슈퍼 소수 중 N번째로 작은 것을 출력하는 프로그램을 작성하세요.

 

첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. ( 1 ≤  T ≤  1000) 그다음 줄부터 총 T개의 줄에 각각 정수 N이 한 줄에 하나씩 주어집니다. ( 1 ≤  n ≤  3000)

 

각 테스트 케이스에서 입력된 N에 대해 N번째 슈퍼 소수를 한 줄에 하나씩 출력하세요.

 

나의 코드

#include <iostream>
#define MAX 500000
using namespace std;
int main(){
	bool A[MAX+1]={1,1};
	int B[MAX+1]={},index=1;
	for (long long i=2;i<=MAX;i++){
		if (A[i]==0){
			B[i]=index;
			index++;
			for (long long j=(long long)i*i;j<=MAX;j+=i){
				A[j]=1;
			}
		}
	}
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for (int i=2;;i++){
			if (A[i]==0 && A[B[i]]==0){
				n--;
				if (n==0){
					cout << i << "\n";
					break;
				}
			}
		}
	}
	return 0;
}

나는 이 코드를 작성하면서 B배열을 만드는 것이 가장 힘들었던 것 같다.

맨 처음에는 B[index]에 i를 넣었다가 시간초과가 나서 포기하려고 했었다.

하지만 계속 고민하다가 i에 index를 넣으면 효율적일 것 같아서 그렇게 하고 정답을 받았다.

 

이번 대회는 만족스러운 것 같다.