[백준] 17435 합성함수와 쿼리 (C++)

문제

17435번: 합성함수와 쿼리 (acmicpc.net)

17435번: 합성함수와 쿼리

 

풀이

정의역과 공역의 범위가 같은 functional graph가 주어졌으므로 무한히 합성가능합니다.

n번 합성한 경우의 함수값을 결정하기 위해 n번 반복을 한다면 Q * n 으로 최대 200,000 x 500,000 의 연산량이 발생해버립니다.
따라서 다른 방법을 사용해야 하고, 이때 희소 배열을 활용한다면 효율적으로 구할 수 있습니다.

 

전형적인 희소배열 구현 문제이므로 구현하는 방법만 안다면 쉽게 구할 수 있습니다.

코드

#include <iostream>
#include <vector>
#include <cmath>

#define MAX_N 500000

using namespace std;

int m;
int q;
vector<vector<int>> sparseTable;

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

    cin >> m;
    int log2maxN = ceil(log2(MAX_N));
    sparseTable.resize(log2maxN, vector<int>(m+1));

    for (int i=1; i<m+1; ++i)
    {
        cin >> sparseTable[0][i];
    }

    for (int i=1; i<log2maxN; ++i)
    {
        for (int j=1; j<m+1; ++j)
        {
            int half = sparseTable[i-1][j];
            sparseTable[i][j] = sparseTable[i-1][half];
        }
    }

    cin >> q;
    while (q--)
    {
        int n, x;
        cin >> n >> x;

        int node = x;
        for (int i=0; i<log2maxN; ++i)
        {
            if (n & 1 << i) // == 1
            {
                node = sparseTable[i][node];
            }
        }

        cout << step << "\n";
    }

    return 0;
}