[알고리즘] 백준 13116번: 30번 (C++)

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

13116번: 30번

이진 트리라서 treeSet 함수에서 세그먼트 트리처럼 구현해주었다.

void treeSet(int node, int pnode) {
	level[node] = level[pnode] + 1;
	parent[node] = pnode;
	if (node * 2 + 1 < MAX) {
		treeSet(node * 2, node);
		treeSet(node * 2 + 1, node);
	}
}

그리고, 최댓값을 찾는 문제라 공통 된 것 중 제일 레벨이 높은 노드를 찾으면 되기 때문에 LCA를 썼다.

[AC 코드]

#include <iostream>
#define MAX (1023 + 1)
using namespace std;

int parent[MAX];
int level[MAX];

void treeSet(int node, int pnode) {
	level[node] = level[pnode] + 1;
	parent[node] = pnode;
	if (node * 2 + 1 < MAX) {
		treeSet(node * 2, node);
		treeSet(node * 2 + 1, node);
	}
}

void swap(int* a, int* b) {
	int* temp = a;
	a = b;
	b = temp;
}

int lca(int a, int b) {
	if (level[a] < level[b]) swap(a, b);
	while (level[a] != level[b]) {
		a = parent[a];
	}

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	return a;
}

int T;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	treeSet(1, 0);
	cin >> T;
	for (int i = 0, a, b; i < T; i++) {
		cin >> a >> b;
		cout << lca(a, b) * 10 << '\n';
	}
	return 0;
}