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

27172번: 수 나누기 게임 (acmicpc.net)

27172번: 수 나누기 게임

처음 수부터 끝 수까지 차례대로 약수를 구한 다음 구한 약수에 대해 카드가 존재한다면 점수를 주는 방식으로 구현해봤다. 다른 사람들의 코드를 보니 해당 카드의 배수로 접근해 그 배수의 값을 가진 카드가 있는지 찾는 코드였다. 이 방식이 더 깔끔해보였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <cmath>
#define ll long long
#define pii pair<int,int>
#define endl '\n'

using namespace std; 

int N;
int num[100000];
bool chek[1000001];
int ans[1000001];
set<int> s;

int main() {
	cin>>N;
	int tmp;
	for(int i = 0; i<N; i++)
	{
		cin>>num[i];
		chek[num[i]]=true;
	}
	for(int i=0; i<N; i++)
	{
		for(int j = 1; j<=sqrt(num[i]); j++)
		{
			if(num[i]%j==0)
			{
				s.insert(j);
				if(j!=num[i]/j&&num[i]!=num[i]/j)
					s.insert(num[i]/j);
			}
		}
		for(auto a : s)
		{
			if(chek[a])
			{
				ans[a]++;
				ans[num[i]]--;
			}
		}
		s.clear();
	}
	for(int i = 0; i<N; i++)
	{
		cout<<ans[num[i]]<<" ";
	}
	return 0;
}