[G1] 백준 17435번 합성함수와 쿼리 C++ LCA, 최소 공통 조상, 희소 배열

리뷰

 

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

문제 분류만 보았을 땐 이게 왜 LCA지? 라는 느낌이 들었지만, 친구에게 설명을 듣고 나서 이해가 되었다.

 

전역 변수

• MAX_N : 주어지는 함수 내 원소의 최대 개수를 저장할 정수형 상수 변수
• LOG : 비트단위로 부모를 탐색할때 사용할 정수형 상수 변수
• m, q : 주어진 원소의 개수를 저장할 변수 m, 쿼리의 개수를 저장할 변수 q
• n, x : 함수를 반복할 회수를 저장할 변수 n, 함수의 초깃값에 넣을 원소의 번호 x
• par : 각 원소의 2^n번째 부모 원소를 저장할 2차원 배열, MAX_N * LOG 크기로 저장한다.

 

함수

1. preprocess

void preprocess()

 

par배열을 초기화 하기 위한 함수

1. 각 원소의 par배열에 2^n번째 부모를 저장하기 위한 전처리를 진행해 준다.
2. j를 1 ~ LOG - 1범위로, i를 1 ~ m범위로 설정한다.
3. i원소의 2^j번째 부모 원소는 i원소의 2^j - 1번째 부모 원소의 2^j - 1번째 부모 원소이다.

 

2. lca

void lca()

 

입력받은 n과 x를 기반으로 f(x)를 n번 수행했을때의 값을 구하는 함수

1. 0부터 LOG - 1번까지 순회하며 n의 비트를 i만큼 시프트 해준다.
2. 만약 i번 시프트 했을때 가장 첫번째 비트가 존재한다면 x를 x의 2^i번째 원소로 변경해 준다.

 

문제풀이

1. m값을 입력 받고, m개의 원소에 대하여 par의 자신의 인덱스에 바로 윗 조상을 입력 받아준다.
2. preprocess함수를 통해 각 원소의 par배열을 초기화 해준다.
3. q값을 입력 받고, q번의 반복문을 수행해 준다, 이후 n과 x값을 입력 받아준다.
4. lca함수를 통해 f(x)가 n번 진행하는 작업을 해준다.
5. x에 저장된 값을 출력해 준다.

 

참고 사항

기본적인 두 노드간 LCA를 구하는 문제보다는 쉽다.

하지만 이걸 LCA라고 생각하고 접목하는 것 자체가 말이 안되게 어려웠던 것 같다.

 

 

정답 코드

#include<iostream>

using namespace std;

const int MAX_N = 200001;
const int LOG = 20;

int m, q, n, x;
int par[MAX_N][LOG];

void preprocess() {
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= m; i++) {
			if (par[i][j - 1] != -1) par[i][j] = par[par[i][j - 1]][j - 1];
		}
	}
}

void lca() {
	for (int i = 0; i < LOG; i++) {
		if ((n >> i) & 1) x = par[x][i];
	}
}

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

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

	preprocess();

	cin >> q;
	while (q--) {
		cin >> n >> x;
		lca();
		cout << x << "\n";
	}
}