[C++] 백준/Gold/27172. 수 나누기 게임

문제: 수 나누기 게임 (백준 27172번)

문제 분석

문제 개요:
n개의 정수가 주어지고, 각 정수에 대해 “나누기 게임” 규칙에 따라 점수를 계산해야 한다.

• 만약 정수 $a$가 주어졌을 때, $a$의 배수 중 입력에 포함된 정수들이 있다면,
  • $a$는 그 배수들을 "나눌 수 있음"으로 처리하여 점수를 얻고,
  • 반대로, $a$가 다른 수의 배수라면 점수를 잃는다.

접근 아이디어:

1. 입력 저장 및 최대값 확인:
   • 입력받은 정수들을 벡터에 저장하고,
     존재하는 수들을 빠르게 확인하기 위해 해시맵(unordered_map<int, bool>)에 기록한다.
2. 배수 관계 계산:
   • 1부터 최대값까지 순회하면서,
     해당 수가 입력에 포함된 경우,
     그 수의 배수들을 탐색하여,
     만약 배수가 입력에 포함되어 있다면,
     배수인 수에서는 점수를 감소, 기준 수에서는 점수를 증가시킨다.
3. 최종 점수 출력:
   • 각 입력 수에 대해, 계산된 점수를 출력한다.

---

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n; 
    cin >> n;
    unordered_map<int, bool> dict; // 입력에 포함된 수를 빠르게 확인하기 위한 자료구조
    vector<int> v1(n);
    int maxVal = 0;
    
    // 입력 받으면서 최대값을 갱신하고, dict에 존재 표시
    for (int i = 0; i < n; i++)
    {
        cin >> v1[i];
        dict[v1[i]] = true;
        maxVal = max(maxVal, v1[i]);
    }
    
    // 각 수의 점수를 저장할 벡터 (배열 크기는 최대값+1)
    vector<int> v2(maxVal + 1);
    
    // 1부터 maxVal까지 순회
    for (int i = 1; i <= maxVal; i++)
    {
        // 만약 i가 입력에 포함되어 있다면
        if (dict[i])
        {
            // i의 배수를 j (i+i 부터 maxVal까지) 순회
            for (int j = i + i; j <= maxVal; j += i)
            {
                if (!dict[j]) continue; // j가 입력에 없으면 건너뜀
                v2[j]--; // j는 i의 배수이므로, j는 점수를 잃는다.
                v2[i]++; // i는 j를 나눌 수 있으므로, i는 점수를 얻는다.
            }
        }
    }

    // 각 입력 수에 대해 최종 점수를 출력
    for (int i = 0; i < n; i++)
    {
        cout << v2[v1[i]] << ' ';
    }
}