[백준] 27172번 수 나누기 게임 C++ 문제풀이

문제 풀이

맨 처음에는 간단하게 이중 for문으로 코드를 작성했는데, 시간 초과로 바로 틀렸다

이중 for문이더라도 에라토스테네스의 체의 시간 복잡도는 O(Nlog(log N)) 이므로 에라토스테네스의 체 방식을 적용해 문제를 해결했다.

card 벡터에 <card 번호, 플레이어 번호>를 저장하고, check 배열에는 카드를 가지고 있는지를 저장, score 배열에는 card 번호에 대한 점수를 계산한다.

그리고 아래의 방식처럼 에라토스테네스의 체 방식을 적용해 점수를 계산한 후 출력해줬다.

	for (int i = 0; i < N; i++) {
		int start = card[i].first * 2;
		while (start <= max_idx) {
			if (check[start] == true) {
				score[start] -= 1;
				score[card[i].first] += 1;
			}
			start += card[i].first;
		}
	}

 

소스 코드

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

vector<pair<int,int>> card; // card 번호와 플레이어 번호를 저장
bool check[10000001]; // 카드를 가지고 있는지 확인
int score[10000001] = { 0 }; // 점수를 계산

bool compare(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}

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

	int N;
	cin >> N;

	int max_idx = 0; //카드 번호 중 가장 큰 수
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		card.push_back(make_pair(a, i));
		check[a] = true;
		max_idx = max(max_idx, a);
	}
	//card를 "낮은 수" -> "높은 수"로 정렬
	sort(card.begin(), card.end()); 
	// 점수를 계산
	for (int i = 0; i < N; i++) {
		int start = card[i].first * 2;
		while (start <= max_idx) {
			if (check[start] == true) {
				score[start] -= 1;
				score[card[i].first] += 1;
			}
			start += card[i].first;
		}
	}
	// 플레이어 번호 순서대로 정렬
	sort(card.begin(), card.end(), compare);

	for (auto x : card) {
		cout << score[x.first] << " ";
	}

	return 0;
}