[백준][C++] 27172: 수 나누기 게임

문제

풀이

• 들어온 수를 하나하나 모두 나누면서 접근하면 시간초과이다.
•  1000000길이의 bool 배열에 입력으로 들어온 인덱스에 해당하는 배열의 값을 true로 세팅한다. 
• 검사할 값의 배수가 입력으로 들어왔는지 확인한다.
• 배수가 들어왔다면 answer에 현재 검사하는 값에 해당하는 배열의 값을 1증가시키고, 배수의 값은 1 감소시킨다.

코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1000001;

bool num[MAX];
int answer[MAX];
vector<int> num_v;

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

    int N;
    int maxi = 0;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        num_v.push_back(temp);

        num[temp] = true;                   // 입력으로 들어온 숫자를 true로 세팅

        maxi = max(maxi, temp);
    }

    for (int i = 0; i < N; ++i)
    {
        int current_num = num_v[i];
        int temp = 2;
        while (current_num * temp <= maxi)
        {
            if (num[current_num * temp])    // 현재 확인하는 숫자의 배수가 입력으로 들어왔다면
            {
                answer[current_num]++;
                answer[current_num * temp]--;
            }

            temp++;
        }
    }

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

    return 0;
}