백준 11812번: K진 트리 (C++)

접근

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

11812번: K진 트리

시간 초과로 고생하고 있었는데 해결을 못하고 있다가 입출력 관련 버퍼 관련된 구문을 추가하여 시간안으로 들어왔다.

분명 제대로 푼 것 같고, 다른 분들 풀이도 확인했는데 문제가 없어서 의아해하고 있던 중, 어이없게 풀려서 허탈했다.

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

왜 이러한 구문을 쓰는지 찾아보았고, 기억을 위해 링크해두겠다.

https://jaimemin.tistory.com/1521

ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유

문제 해결은 LCA 알고리즘을 이용하되, 적은 에너지 방법으로 채워진 트리의 특성을 이용해 숫자를 계산하여 부모 노드를 찾는 방식으로 문제를 해결하였다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

#define endl '\n'

long long int N;
int K, Q;
long long int d1, d2;

// d1, d2에 a, b 의 깊이를 저장해주는 함수
void FindDepth(long long int a, long long int b) {
    long long int d = 0;
    long long int val = 1;
    while (d1 == -1 || d2 == -1) {
        a -= val;
        b -= val;
        if (a <= 0 && d1 == -1) d1 = d;
        if (b <= 0 && d2 == -1) d2 = d;
        val *= K;
        d++;
    }
}

// a, b의 공통 부모까지의 거리를 카운트하여 dist 계산하는 함수
long long int Solve(long long int a, long long int b) {
    if (K == 1) return abs(a - b);
    d1 = -1;
    d2 = -1;
    FindDepth(a, b);
    long long int dist = 0;
    // 둘의 깊이가 같아질 때까지 더 깊은 쪽을 한칸씩 올린다.
    while (d1 != d2) {
        if (d1 > d2) {
            a = (a - 2) / K + 1;
            dist++;
            d1--;
        } else {
            b = (b - 2) / K + 1;
            dist++;
            d2--;
        }
    }
    // 공통 부모를 만날때까지 양쪽을 한칸씩 올린다.
    while (a != b) {
        a = (a - 2) / K + 1;
        b = (b - 2) / K + 1;
        dist += 2;
    }
    return dist;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K >> Q;
    long long int a, b;
    for (int i = 0; i < Q; i++) {
        cin >> a >> b;
        cout << Solve(a, b) << endl;
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!