레야몬

[C++] 17435번 합성함수와 쿼리 - 자료 구조, 희소 배열 본문

알고리즘/백준

[C++] 17435번 합성함수와 쿼리 - 자료 구조, 희소 배열

Leyamon 2022. 12. 20. 16:03

1. 문제

  • 함수 f:{1, 2, ..., m} -> {1, 2, ..., m}
    • f1(x)=f(x)
    • fn+1(x)=f(fn(x))
  • n, x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하시오

<입력>

  • - 1 -   m(1m200,000)
  • - 2 -   f(1), f(2), ..., f(m)
  • - 3 -   쿼리의 개수 Q(1Q20,000)
  • - Q개의 줄 -   정수 n,x(1n500,000,1xm)

<출력>

  • 주어지는 n, x마다 fn(x) 출력

2. 재정의

  • X

3. 해결 방법

  • f[i][k] sparse array

4. 실수한 점, 개선할 점

  • input()을 안으로 뺐다고 시간이 30ms나 차이가 남. 앞으로 함수 안 빼려고 해야겠음

 

<코드>

#include <iostream>
#include <cmath>

using namespace std;

const int MAX_M = 200001;
const int MAX_K = (int)ceil(log2(MAX_M))+1;

// <문제>
// 정의역 원소 개수 M, 쿼리의 개수 Q
int M, Q;

// Sparse Array
int f[MAX_K][MAX_M];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> M;
    // Sparse Array 만들기
    for(int i=1; i<=M; i++)
        cin >> f[0][i];
    for(int k=1; k<MAX_K; k++)
        for(int i=1; i<=M; i++)
            f[k][i] = f[k-1][f[k-1][i]];
    cin >> Q;
    
    while(Q--) {
        int n, x;
        cin >> n >> x;
        for(int i=0; n; i++) {
            if(n%2)
                x = f[i][x];
            n >>= 1;
        }
        cout << x << '\n';
    }
    
    return 0;
}

 

<문제 바로가기>

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

 

17435번: 합성함수와 쿼리

함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는

www.acmicpc.net

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.

Comments