[Algorithm]Baekjoon 27172번 : 수 나누기 게임

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

27172번: 수 나누기 게임

 
 
using namespace std;
 
 
 
int n;
bool isPicked[1000001] = { 0 };
int scores[1000001] = { 0 };
vector<int> cardNums;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
        
        isPicked[num] = true;
        cardNums.push_back(num);
    }
 
    for (int i = 0; i < cardNums.size(); ++i)
    {
        int num = cardNums[i];
 
        for (int j = num * 2; j <= 1000000; j += num)
        {
            if (isPicked[j])
            {
                ++scores[num];
                --scores[j];
            }
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", scores[cardNums[i]]);
    }
}
 

 

각 숫자카드를 들고있는 플레이어들은 자기자신을 제외한 모든 플레이어와 대결을 하고 일정한 조건에 의해 승,패를 나눈다음 점수를 ++하거나 --한 다음, 마지막으로 모든 플레이어들의 점수를 출력해야하는 문제이다.

 

승패를 나눌 조건이란, A라는 플레이어의 숫자로 B라는 플레이어의 숫자를 나눴을 때 나머지가 0이라면 A가 이기고 B가 패배한다. 승자는 1점을 획득하고 패자는 1점을 잃는다.

 

일단 모든 숫자는 딱 한가지씩만 있으니, 처음에 입력받을 때 각 숫자에 대해 플레이어가 들고있는 숫자인지 모두 체크해준다. (isPicked 변수)

 

이후, 에라토스테네스의 체 개념을 적용한다.

플레이어들이 들고있는 각 숫자들을 순회하면서 아래와 같은 로직을 진행한다.

들고있는 숫자의 배수만큼 건너뛰며 반복문을 순회하면서,  그 배수가 특정플레이어가 들고있는 숫자라면 특정플레이어는 반드시 패배하고 기준이 되는 플레이어는 반드시 승리하기 때문에 그 결과를 반영한다.

기준이 되는 숫자의 배수로 건너뛰기 때문에, 반드시 A의 숫자로 B의 숫자를 0으로 나누어 떨어지게 하는 것이 가능하다.