[c++] 백준 27172번: 수 나누기 게임 (수학)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

n명의 플레이어가 1부터 1000000 사이의 수 하나를 각각 가질 때, 게임이 종료된 후 각 플레이어의 점수를 구하여라

 게임 규칙은 다음과 같습니다.

1. 한 플레이어는 다른 모든 플레이어와 한 번씩 결투를 진행한다.
2. 결투는 공격하는 플레이어의 수로 공격을 받는 플레이어의 수를 나누었을 때, 나머지가 0이면 공격자가 승리한다. 나누어 떨어지지 않으면 무승부이다.
3. 승리한 플레이어는 1점을 얻고, 패배한 플레이어는 1점을 잃는다.(점수는 음수도 가능하다.)

---

시간복잡도 어림하기

브루트 포스 알고리즘

 가장 단순한 알고리즘을 생각해 보면, 각 플레이어의 수를 배열에 저장해 두고, 두 개의 for 루프를 사용하여 각 경우마다 직접 나누어 승패를 가리면 됩니다. 이 로직은 O(n^2)의 시간복잡도를 가지게 되는데, 문제에서 n의 최댓값이 100,000 이고 n^2 = 10,000,000,000(백억)입니다. 따라서 각 수를 나누어 승자를 가리는 방식은 제한 시간 내에 문제를 해결할 수 없습니다.

---

알고리즘 설계하기

  결국 제한 시간 내에 문제를 해결하기 위해서는 반복 횟수를 줄여야 합니다. 플레이어가 점수를 얻는 방식을 다시 생각해보면 자신의 수가 다른 플레이어의 수를 나누어 떨어지게 하면 점수를 얻습니다. 다시 말해, 상대 플레이어의 수가 자신이 가진 수의 배수라면 점수를 얻게 됩니다.

1부터 1,000,000까지의 수에서 어떤 수 x의 배수의 개수는 1,000,000 / x 입니다.
x = 1일 때 1,000,000개
x = 2일 때 500,000개
x = 3일 때 333,333개
x = 4일 때 250,000개
...
x = 10일 때 100,000개
...
x = 100일 때 10,000개
...
x = 1,000,000일 때 1개

 기존 로직은 for 루프를 두 개 중첩하여 각 수의 값을 모두 비교하는 방식이었습니다. 이 방식은 100,000 + 99,999 + 99,998 + ... + 2 + 1번 반복하게 됩니다.

 이 방식과 위 배수를 구하는 방식을 보면, 배수를 미리 구하는 방식이 훨씬 반복 횟수가 적다는 것을 추측할 수 있습니다. x = 10전에는 10만 보다 큰 수였지만, 그 이후에는 횟수가 빠르게 감소하기 때문입니다. 따라서 배수를 미리 구해 승자를 판단하는 로직을 사용해야 합니다.

 이를 어떻게 활용할 수 있을까요? 각 수의 배수를 구하면서 해당 배수가 어떤 플레이어가 가지고 있는지 판단하면 됩니다. 따라서 처음 플레이어에게 수를 배분할 때 어떤 수가 배분되었는지 미리 확인을 해야 합니다. 코드로는 다음과 같이 표현할 수 있습니다.

cin >> n;
for(int i = 0; i < n; i++){
    cin >> a[i];
    visited[a[i]] = 1; //플레이어가 받은 수 체크
}
for(int i = 0; i < n; i++){
    int num = a[i];
    for(num의 배수 계산){
        if(visited[배수] == 1){
            승리 플레이어 점수 증가, 패배 플레이어 점수 감소
        }
    }
}

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int n, a[100004], ret[1000004], visited[1000004];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        visited[a[i]] = 1; //플레이어가 받은 수 체크
    }
    for(int i = 0; i < n; i++){
        int num = a[i];
        for(int j = num * 2; j <= 1000000; j += num){ //num의 배수 탐색 로직
            if(visited[j] == 1){ //현재 수가 플레이어가 가지고 있다면
                ret[num]++; ret[j]--; //num의 점수 증가, j의 점수 감소
            }
        }
    }
    //i플레이어가 가진 수 a[i]의 점수 ret[a[i]]를 출력
    for(int i = 0; i < n; i++) cout << ret[a[i]] << " ";
    return 0;
}

 위 코드에서 주의해야 하는 점은 ret 배열은 각 플레이어의 점수가 아니라 수에 대한 점수입니다. 예를 들어 입력이 3 4 12라면 ret[3] = 2, ret[4] = 2, ret[12] = -2로 저장됩니다. 문제에서는 플레이어의 점수를 출력하라고 했으므로 ret[플레이어가 가진 수]로 결과를 출력해야 합니다.

---