[백준] 11812 K진 트리

일반적으로 이러한 문제를 공통조상문제 LCA(Lowest Common Ancestor)라고 한다고 한다. 해당 문제의 경우 K진 트리가 가지고 있는 특성이 있다고 한다. 그래서 해당 식을 통해서 쉽게 풀 수 있었다.

이거 안보고 할려다가 4시간 가까이 날리면서 시간초과가 났다. 이런 문제 좀…. 별루….ㅠㅠ

#include <cmath>
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

typedef long long ll;

ll N, K, Q, NODE1, NODE2;

void search() {
  ll node1, node2;
  if (NODE1 >= NODE2) {
    node1 = NODE1;
    node2 = NODE2;
  } else {
    node1 = NODE2;
    node2 = NODE1;
  }
  ll cnt = 0;
  if (K == 1) {
    cout << node1 - node2 << endl;
    return;
  }

  while (node1 != node2) {
    long max_num = max(node1, node2);
    node2 = min(node1, node2);
    node1 = (max_num - 2) / K + 1;
    cnt++;
  }
  cout << cnt << endl;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> K >> Q;

  while (Q--) {
    cin >> NODE1 >> NODE2;
    search();
  }
}

[백준] 11812 K진 트리

Abstract

[백준] 11812번 K진 트리

알고리즘 유형

문제 이해

풀이방법