[백준 27172번] 수 나누기 게임 (C++)

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

27172번: 수 나누기 게임

문제는 자신의 카드로 상대방의 카드를 나누어 떨어뜨릴 수 있으면 자신이 포인트를 1점 획득하고, 상대방이 내 카드를 나누어 떨어뜨리면 나는 1점을 잃는다. 그 이외의 상황에서는 점수 변화가 없다.

문제는 N이 최대 100,000이라는 것인데 2중 포문으로 모든 플레이어와 한번씩 대결한 결과를 비교하면 시간초과가 난다.

(C++은 1초에 10억개 정도의 연산을 수행한다)

 

그래서 에라토스테네스의 체와 비슷한 방식으로 문제를 해결할 수 있다.

에라토스테네스의 체는 2부터 끝 범위까지 해당 숫자의 배수를 소수가 아님을 표시하면서 소수를 구한다.

예를 들어 4,6,8,10 ...은 소수가 아님이 i=2일때 정해지고 3,9,15, ... 등이 i=3일때 소수가 아님이 정해진다.

에라토스테네스의 채를 한번도 구현해보지 않았다면 소수를 구할때 유용하니 꼭 공부해서 구현해보는 것을 추천한다.

 

이와 비슷한 방식으로 자신의 배수를 모두 표시함으로써 입력값에 자신의 배수가 존재한다면 1점을 획득하는 방향으로 코드를 짜면 된다.

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\n"
using namespace std;

int main() {
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int n, num;    cin >> n;
    int card[1000001];
    int check[1000001];
    int player[1000001]={0,};

    for(int i=0;i<n;i++){
      cin>>card[i];
      check[card[i]]=1;
    }

	//에라토스테네스의 채
    for(int i=0;i<n;i++){
      num=card[i];
      for(int j=num*2;j<1000001;j+=num){
        if(check[j]){
          player[num]++;
          player[j]--;
        }
      }
    }

    for(int i=0;i<n;i++){
      cout << player[card[i]] << " ";
    }
}