백준 27172번 수 나누기 게임 - C++ 풀이

---

 

1. 약수&배수 관계인 수들의 결투만 의미가 있다. 
2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다.
3. 각 xi에 대해 xi의 모든 약수들과 결투한다.

 

1. 약수&배수 관계인 수들의 결투만 의미가 있다. 

 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자.

 

 

2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다.

 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다.

 

2. 각 xi에 대해 xi의 모든 약수들과 결투한다.

 i가 x의 약수인 경우, x는 i의 배수이다. 따라서 모든 수들의 약수를 찾으면 모든 약수&배수 관계를 찾은 것이다. 모든 수 xi에 대해 xi의 모든 약수들을 구하여 결투시키자. 약수인 i는 점수가 +1되고, 배수인 x는 -1이 된다.

 

---

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

using namespace std;

const int MAX_X = 1'000'000;

int N;
vector<int> players;
bool exists[MAX_X+1];
int scores[MAX_X+1];

void findDivisor(int x) {
    for (long long i=1; i*i <= x; i++) {
        if (x % i) continue;
        
        if (exists[i]) {
            scores[x]--;
            scores[i]++;
        }
        
        int q = x / i;
        if (exists[q] && q != i) {
            scores[x]--;
            scores[q]++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    players.resize(N);
    for (int i=0; i<N; i++) {
        cin >> players[i];
        exists[players[i]] = true;
    }
    
    for (int i=0; i<N; i++) {
        for (int j=i*2; j<=MAX_X; j+=i) {
            if (exists[i] && exists[j]) {
                scores[i]--;
                scores[j]++;
            }
        }
    }
    
    for (int i=0; i<N; i++) {
        cout << scores[players[i]] << " ";
    }
}