[백준/C++] 27172 수 나누기 게임

https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

 

1~1,000,000 사이의 수 중 하나씩 나눠갖고

다른 플레이어의 수를 내가 가진 수로 나눌 수 있으면 +1점,

다른 플레이어의 수로 나누어 떨어지면 -1점 

 

 

 

[풀이 과정]

우선 처음에는 플레이어의 수가 100,000이고 제한시간이 1초이기 때문에 for문 반복으로

한사람씩 계속 비교한다고 생각했을때, 100명이 비교를 하면 for문 반복이 100->99->98의 식으로 등차수열을 하기 때문이었다. 그래서 n(n+1)/2의 시간복잡도가 걸려 50억? 정도가 나와서 다른 방법을 생각했어야 했다. 

그래서 분류표를 보니까 보이는게 에라토스테네스의 체 였는데, 예전에 한 번 봤었는데 기억이 안나서 못품 ㅎ..

 

에라토스테네스의 체 시간 복잡도 : O(nloglogn) 

 

 

#include <bits/stdc++.h>

using namespace std;

vector<int> v; // 플레이어의 카드를 받는다.
int cards[1000002];
int scores[1000002];
int N;

int main() {
	cin >> N;
	int n;

	fill(scores,scores + 1000002, 0);
	for (int i = 0; i < N; i++) {
		cin >> n;
		v.push_back(n);
        //나눠가진 숫자임을 표기.
		cards[n] = 1;
	}
    
    // 플레이어 반복 > i > vector에 있는 수를 꺼내 씀.
	for (int i = 0; i < N; i++) {
    	// vector에 있는 카드의 배수를 구한다.
		for (int j = v[i]*2; j < 1000002; j+=v[i]) {
			// 누군가가 가지고 있는 숫자라면 점수 표기
            
            if (cards[j]){
				scores[j]--;
				scores[v[i]]++;
			}
		}
	}
	for (auto i : v) {
		cout << scores[i] << ' ';
	}

	
}