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

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때, 빠르게 해결하기 위해 Cycle이 생기는 순간을 기록해야하나? 의문이 들었다.

그런데 아무리 생각해도 Cycle을 판단하는데 시간이 오래 걸릴 것으로 보여 다른 방법을 고민했다.

 

중간에 다른 사람의 힌트를 보니 DP를 이용해 문제를 푼 것을 보고 해결을 할 수 있었다.

 

함수를 2^k번 적용한 값을 저장하는 DP를 만들면, DP배열을 이용해 빠르게 계산을 할 수 있다.

 

함수를 2^k번 적용한 DP배열을 만드는 방법도 간단하다. x라는 수를 2^k번 적용해 x1이라는 수가 나오면, x1을 다시 2^k번 적용한 수 x2를 구한다. 그러면 x라는 수를 2^(k+1)번 나온 수가 x2가 되는 것이다.

이렇게 DP 배열을 만들고 나면 k에 따라 함수를 몇 번 적용할 것인지 DP배열을 이용해 계산하면 된다.

 

ex) n이 10 이라면, 함수를 2^3, 2^1번 적용한 값을 DP배열에서 찾으면 된다.

 

여기서 빠르게 계산하기 위해 n을 2진법으로 생각해 계산했다.

 

n이 10이라면 2진법으로 변경할 경우 1010이므로 x라는 수를 2^1번 함수를 적용해 x1을 구하고 x1의 수에 함수를 2^3번 적용한 값을 구하면 된다.

이러한 과정을 shift 연산으로 구현했다. (지금 생각해보니 2로 나누는 것과 똑같다.)

 

 

​

[아이디어 정리]

1. 함수를 2^k번 적용한 값을 저장하는 2차원 DP배열을 만든다.
2. DP배열에서 빠르게 수를 찾기 위해 n을 이진수로 생각해 빠르게 계산한다.

 

 

 

Code

 

 

#include<iostream>
#include <string>
#include <vector>
using namespace std;

int calc(vector<vector<int>>& dp, int n, int x, int dpt) {
    if (n==1)
    {
        return dp[dpt][x];
    }
    
    if (n % 2 == 1) {
        return calc(dp, n>>1, dp[dpt][x],dpt+1);
    }
    else {
        return calc(dp, n >> 1, x, dpt + 1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int m,q;
    cin >> m;
    vector<vector<int>> dp(20, vector<int>(m+1,0));
    for (int i = 1; i <= m; i++) {
        cin >> dp[0][i];
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
    cin >> q;
    int n, x;
    for (int i = 0; i < q; i++) {
        cin >> n >> x;
        cout << calc(dp, n, x,0)<<"\n";

    }

    return 0;
}

 

---

정말 오랜만에 알고리즘 문제를 풀었더니, 머리속에 있는 방법을 코드로 구현하는데 생각보다 시간이 많이 걸렸다.

심지어 헷갈리기까지 해버렸다...

 

다시 꾸준히 시작해야지

 

https://www.acmicpc.net/problem/17435