백준 - 27172 수 나누기 게임

 

해결과정 - 에라스토테니스의 체?

간략하게 정리하면 한 플레이어당 다른 모든 플레이어와 대결을 한뒤 내 카드의 수가 상대 플레이어의 카드수를 나누어 떨어지게 만들수 있으면 1점을 얻고 패배한 플레이어는 1점을 잃는 것이였다.

 

이번에도 n^2방식으로 서로 대결을 나누도록 했지만 역시 시간초과가 발생하였다.

 

어제 풀었던 에라스토테니스의 체와 비슷한 방식으로 내 카드에 나눠떨어지는 것들을 계산해 보면 좋을 거라고 생각하였다. 따라서 100만가지의 숫자중 존재하는 카드와 해당 인덱스를 캐싱한뒤 현재 점수를 계산하니 해결이 되었다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <unordered_map>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

pair<int,int> hasValue[1000001];
int arr[100000];
int result[100000];

int main() {
    FAST;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
		cin >> arr[i];
		hasValue[arr[i]].first++;
		hasValue[arr[i]].second = i;
	}
    
    for (int i = 0; i < n; i++) {
        int value = arr[i];

        int j = 2;
        int count = 0;
        while (arr[i] * j <= 1000000) {
            int value = arr[i] * j;
            if (hasValue[value].first != 0) {
                result[hasValue[value].second]--;
                count++;
			}
            j++;
        }
        result[i] += count;
    }

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

    return 0;
}

 

후기

창의성이 필요한 문제 였다

 

비염때문에 진짜 미치겠다 ㅠㅠ