BOJ 27172 - 수 나누기 게임

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

 

1차 시도

카드를 서로 비교하여, 나누어 떨어지는지 비교하면 된다.

카드가 100000장 이기 때문에 브루트포스로 모두 비교하면 시간초과가 발생한다.

따라서, 비교할 필요가 없는 카드를 선별하면 된다고 판단.

 

비교할 필요가 없는 카드 = 소수

이므로 에라토스테네스의 체를 이용하여 소수를 선별하고, 해당 플레이어는 패스하도록 설계했다.

 

당연하게도 시간초과.

왜냐하면 최악의 경우(소수가 없는 경우) 모든 수를 비교하기 때문에 O(N^2)이 걸린다.

 

접근

소수를 찾고 진행하는 대신 플레이어 숫자의 배수인 카드를 가진 플레이어를 찾는 것이 훨씬 빠르게 작동한다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

#define MAX 1000001
#define ll long long
using namespace std;

int n;
vector<int> player;
int score[MAX];
bool chk[MAX];

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        player.push_back(tmp);
        chk[tmp] = true;
    }

    for(int i=0;i<player.size();i++) {
        for(int j = player[i]*2; j<MAX;j+=player[i]) {
            if(chk[j]) {
                score[player[i]]++;
                score[j]--;
            }
        }
    }

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

    return 0;
}