[백준 27172] 수 나누기 게임

 

 수학 기반 구현 문제이다. N이 최대 100,000으로 모든 플레이어를 기준으로 브루트 포스를 사용하면 시간초과가 나고, 모든 결투를 기준으로 해도 시간 초과가 난다(n*(n-1)/2). 따라서 모든 경기를 계산하지 않아야 한다.

 처음엔 좀 감이 오지 않았는데, 무승부인 경우 점수 변화가 없다는 부분에 주목해서 솔루션을 떠올렸다. 무승부가 아닌 경기만 점수 계산을 하면 되지 않을까? 하는 어프로치였다. 그렇다면 무승부가 아닌 경기를 어떻게 판별할 수 있을까만 생각하면 되었다.

 그 해답은 간단한데, 플레이어가 가진 수를 인수로 가질 수 있는 수를 가진 플레이어와만 결투를 하면 된다. 서로소인 경우 무승부가 되고, 플레이어가 가진 수의 인수가 될 수 있는 수를 가진 플레이어와는 결투했을 때 점수의 변동이 있으나, 어차피 모든 플레이어에 대해 탐색할 것이므로 그쪽은 계산하지 않아도 무방하다.

 

 글로 써두면 조금 복잡하긴 하지만, 간단하게 이야기 해서 플레이어가 가진 수 num에 대해 num * 2, num * 3, ... , num * i 꼴이 되는 수를 가진 플레이어랑만 결투를 하겠다는 소리다. 이 때 당연히 현재 탐색 중인 플레이어는 점수를 획득하고, 결투하는 플레이어는 점수를 잃게 된다. 

 배수가 되는 숫자를 가진 플레이어가 있는지는 자료구조를 이용해서 다양하게 접근 가능한데, 나는 숫자의 최대가 1,000,000이라 그냥 인덱스 리스트를 사용했다. 리스트의 인덱스는 1~1,000,000 범위의 숫자를 의미하며 그 값이 초기 값인 0이 아니라면, 입력 받은 숫자 중 해당 숫자가 해당 값 번 째에 등장했음을 의미한다.

 

 이제 각 플레이어 대해, 가진 숫자의 배수를 가진 플레이어가 있는지 확인하고 유의미한 결투만 계산할 수 있게 되었으므로, 그대로 구현해서 무난하게 해결할 수 있었다. 뭔가 평소에 자주 사용하던 로직이나 접근법이 아니라서 아이디어를 떠올리는 것이 은근히 오래 걸린 것 같다.

 

#include <iostream>

using namespace std;

int indList[1000001];
int numList[100001];
int scoreList[100001];

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

    int n;
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> numList[i];
        indList[numList[i]] = i;
    }

    for(int i=1; i<=n; i++) {
        int num = numList[i];
        for(int j=2; j*num<=1000000; j++) {
            if(indList[j*num]!=0) {
                scoreList[i]++;
                scoreList[indList[j*num]]--;
            }
        }
    }

    for(int i=1; i<=n; i++) {
        cout << scoreList[i] << " ";
    }

}