백준 27172 C++

yun·2023년 12월 23일

C++

목록 보기

10/41

에라토스테네스의 체
- 소수(Prime Number, 1과 자기자신으로만 나누어지는 수)를 찾는 알고리즘
- 단계
  1) 2부터 N까지의 모든 수를 소수로 가정
  2) 2부터 시작해서 배수 제거: 2를 제외한 2의 배수는 모두 소수가 아님 -> 반복
  3) 남아있는 모든 수는 소수
- 이론적으로 시간 복잡도가 O(N log log N)
  - 전체 숫자가 N개, 2부터 p의 배수까지 찾는다고 하면
  - 전체 연산은 N/2 + N/3 + N/4 + ... + N/p = N(1/2 + 1/3 + 1/4 + ... + 1/p)번

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_NUM = 1000001;

int PLAYERS;

vector<int> card_numbers;
bool if_player_has_card[MAX_NUM];
int scores[MAX_NUM];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
	cin >> PLAYERS;

	for (int i = 0; i < PLAYERS; i++)
	{
		int card_num;
		cin >> card_num;

		// vector에 값을 추가할 때, push_back이 아닌 emplace_back을 사용하면 벡터에 직접 객체를 생성하여 추가
        // 값을 복사하지 않으므로 더 효율적(단순한 데이터타입이면 큰 차이는 없음)
		card_numbers.emplace_back(card_num);
		if_player_has_card[card_num] = 1;
	}

	// PLAYERS의 숫자만큼 반복하므로 O(N)의 시간복잡도
	for (int i = 0; i < PLAYERS; i++)
	{
    	// 최악의 경우 O(MAX_NUM * (1/2 + 1/3 + ... + 1/(MAX_NUM-1)))
        // = 조화급수(harmonic series)
        // = O(logN)의 시간복잡도
		for (int j = card_numbers[i] * 2; j < MAX_NUM; j += card_numbers[i])
		{
			if (if_player_has_card[j])
			{
				scores[card_numbers[i]]++;  // 소수를 가진 사람이 승리
				scores[j]--;  // 배수를 가진 사람은 패배
			}
		}
	}  // 2중 for문을 사용하였으므로 전체 풀이는 O(N*logN)의 시간복잡도를 가진다.

	for (int i = 0; i < PLAYERS; i++)
		cout << scores[card_numbers[i]] << " ";

	return 0;
}