(C++) 백준 2960번 [에라토스테네스의 체]

안녕하세요 평범한 컴공생입니다.

 

오늘은 백준 2960번 에라토스테네스의 체 문제 알고리즘 포스팅을 해보겠습니다.

 

실버 4 난이도의 문제입니다.

1. 문제 해결 방법 구상하기

 -  N과 K의 값을 먼저 입력받는다.

 - 2부터 시작해서 3, 4, 5 ... 와 같이 1씩 값을 올려주며 그 수의 배수인 값을 지워주어야한다.

 - 단, 2, 4, 6, ... 과 같이 2의 배수를 지웠는데 3, 6, 9 ,... 처럼 6이 중복이 된다면 6을 또 지워줄 수 없다.

 - 그러므로 그 수를 지우기 전에 앞에서 지웠는지 확인을 해주어야 한다.

 - 확인했는데 앞에 그 수가 없다면 지워준다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>

int main()
{
	using namespace std;
	int num[1000] = { 0, }; // 지운 숫자의 배열

	int N, K, cnt;
	cin >> N >> K;

	int erase = 0;
	for (int i = 2; i <= N; i++)
		for (int j = i; j <= N; j = j + i)
		{

			cnt = 0;
			for (int x = 0; num[x] != 0; x++)
			{
				if (num[x] == j)
					cnt++; // cnt를 통해 앞에서 그 수가 있었는지 확인
			}
			if(cnt==0)
				num[erase++] = j;
		}
	cout << num[K - 1] << endl; // num[0]부터 지워진 첫번째 숫자이므로 -1 해준값을 출력

	return 0;
}

 

생각보다 쉽게 풀 수 있었던 문제였다.

 

// 피드백 및 문제사항 제기 언제든지 감사히 받겠습니다.