[백준 C++] 27172 수 나누기 게임 - 에라토스테네스의체

27172번: 수 나누기 게임

#include <iostream>
#include <vector>
using namespace std;

int Players[1000001];
vector<int> Cards;
vector<int> Scores;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 1; i <= 1000000; ++i)
	{
		Players[i] = -1;
	}

	int N;
	cin >> N;
	Cards.reserve(N);
	Scores.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int Card;
		cin >> Card;
		Players[Card] = i;
		Cards.emplace_back(Card);
		Scores.emplace_back(0);
	}

	for (const int& Card : Cards)
	{
		for (int i = 2; Card * i <= 1000000; ++i)
		{
			int OpponentCard = Card * i;
			if (Players[OpponentCard] >= 0)
			{
				++Scores[Players[Card]];
				--Scores[Players[OpponentCard]];
			}
		}
	}

	for (const int& Score : Scores)
	{
		cout << Score << ' ';
	}
}

---

 

에라토스테네스의 체 방법을 사용해서 푸는 정수론 유형의 문제입니다.

 

모든 쌍의 플레이어를 일일이 비교하게 되면 O(N^2)의 시간 복잡도가 되는데,

주어진 최대 플레이어의 수가 크기 때문에 해당 방식을 이용할 수 없습니다.

 

따라서 각 플레이어의 카드를 한번씩만 탐색하면서,

현재 카드의 배수 중에 다른 플레이어 카드가 존재하면 해당 두 플레이어의 점수를 갱신해주는 방식으로

에라토스테네스의 체 방식을 응용해서 풀어야 합니다.