득이공간
[백준 C++] 27172 수 나누기 게임 - 에라토스테네스의체 본문
#include <iostream>
#include <vector>
using namespace std;
int Players[1000001];
vector<int> Cards;
vector<int> Scores;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
for (int i = 1; i <= 1000000; ++i)
{
Players[i] = -1;
}
int N;
cin >> N;
Cards.reserve(N);
Scores.reserve(N);
for (int i = 0; i < N; ++i)
{
int Card;
cin >> Card;
Players[Card] = i;
Cards.emplace_back(Card);
Scores.emplace_back(0);
}
for (const int& Card : Cards)
{
for (int i = 2; Card * i <= 1000000; ++i)
{
int OpponentCard = Card * i;
if (Players[OpponentCard] >= 0)
{
++Scores[Players[Card]];
--Scores[Players[OpponentCard]];
}
}
}
for (const int& Score : Scores)
{
cout << Score << ' ';
}
}
에라토스테네스의 체 방법을 사용해서 푸는 정수론 유형의 문제입니다.
모든 쌍의 플레이어를 일일이 비교하게 되면 O(N^2)의 시간 복잡도가 되는데,
주어진 최대 플레이어의 수가 크기 때문에 해당 방식을 이용할 수 없습니다.
따라서 각 플레이어의 카드를 한번씩만 탐색하면서,
현재 카드의 배수 중에 다른 플레이어 카드가 존재하면 해당 두 플레이어의 점수를 갱신해주는 방식으로
에라토스테네스의 체 방식을 응용해서 풀어야 합니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1806 부분합 - 투포인터 (1) | 2024.02.22 |
---|---|
[백준 C++] 1647 도시 분할 계획 - 최소신장트리 (1) | 2024.02.22 |
[백준 C++] 2467 용액 - 투포인터 (0) | 2024.02.21 |
[백준 C++] 2166 다각형의 면적 - 기하학 (1) | 2024.02.21 |
[백준 C++] 18115 카드 놓기 - 덱 (0) | 2024.02.20 |