문제 간략 설명

게임을 시작하기 전 각 플레이어는 1부터 1,000,000 사이의 수가 적힌 서로 다른 카드를 한 장씩 나누어 가진다. 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 한다. 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나느맨 나머지가 0이면 승리한다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어떨어지면 패배한다.

풀이 방법

arr[]에 플레이어의 점수를 저장한다. num[]에 플레이어가 있는지 없는지 저장한다. vec에 플레이어의 숫자를 저장한다.

vec을 돌면서 vec[i] *j <= 1,000,000까지 돌면서 num[vec[i] * j]*가 존재하면 arr을 증감시키고, 없으면 넘어간다.

최종적으로 arr[vec[i]]를 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;

int arr[1000001] = {0};
bool num[1000001] = {0};
vector<int> vec;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		int input;

		cin >> input;

		num[input] = true;
		vec.push_back(input);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 1; vec[i] * j <= 1000000; j++) {
			if (!num[vec[i] * j]) continue;
			arr[vec[i]]++;
			arr[vec[i] * j]--;
		}
	}

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

	return 0;
}

Key Points