레야몬
[C++] 17435번 합성함수와 쿼리 - 자료 구조, 희소 배열 본문
1. 문제
- 함수 f:{1, 2, ..., m} -> {1, 2, ..., m}
- n, x가 주어질 때
를 계산하는 쿼리를 수행하시오
<입력>
- - 1 -
- - 2 - f(1), f(2), ..., f(m)
- - 3 - 쿼리의 개수
- - Q개의 줄 - 정수
<출력>
- 주어지는 n, 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
※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 3977번 축구 전술 - 그래프 이론, 강한 연결 요소 (0) | 2022.12.21 |
---|---|
[C++] 4196번 도미노 - 그래프 이론, 강한 연결 요소 (0) | 2022.12.20 |
[C++] 13511번 트리와 쿼리 2 - 자료 구조, 트리, 최소 공통 조상, 희소 배열 (0) | 2022.12.20 |
[C++] 3665번 최종 순위 - 그래프 이론, 위상 정렬 (0) | 2022.12.18 |
[C++] 1766번 문제집 - 자료 구조, 그래프 이론, 우선순위 큐, 위상 정렬 (0) | 2022.12.18 |