[백준 27172번] 수 나누기 게임 (C++)

문제링크 : https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];
int visited[1000001];
int result[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, maxV=0;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        visited[arr[i]]=1;
        maxV = max(maxV, arr[i]);
    }

    for(int i=0; i<N; i++)
    {
        if(arr[i] == maxV) continue;
        for(int j=arr[i]*2; j<=maxV; j+=arr[i]) //현재 수의 배수가 있는지 확인
        {
            if(!visited[j]) continue; //없으면 패스
            result[arr[i]]++; //있으면 승리하는 수 (현재 수)
            result[j]--; //패배하는 수 (현재 수의 배수)
        }
    }

    for(int i=0; i<N; i++)
    {
        cout << result[arr[i]] << " " ;
    }

    return 0;
}

현재 입력받은 수에 대해서 나머지 입력받은 값 내에 배수가 존재하는지 확인하면 되는 문제이다.

입력받는 배열, 해당 값 존재 여부 확인용 배열, 결과용 배열 이렇게 3가지를 사용한다.

 

현재 입력받은 수에 대해서 나머지에 약수가 존재한다면 현재 값이 질 것이고,

현재 입력받은 수에 대해서 나머지에 배수가 존재한다면 현재 값이 이길 것이다.

 

입력받은 값을 모두 확인해야하는데 2중 반복문으로 현재 값에 대해 배수가 존재하는 지를 확인해줬다.

만약 현재 값에 대한 배수가 나머지 입력받은 값 내에 존재한다면 현재 값은 결투에 승리하여 1점을 얻을 것이다.

그러면 나머지 값(배수에 해당하는 수)은 결투에서 진 것이므로 -1점을 갖게 된다.

무승부 일 경우에는 양쪽모두 변화가 없으므로 딱히 무엇을 할 필요가 없다.

 

그리고 배수를 확인할 때 입력받은 값의 최대값까지만 확인해주면 된다. (이후의 값은 의미가 없음)

최대값일 때는 나머지 값내에 배수가 존재할 수가 없으므로 continue로 스킵해줬다.