[백준 Gold 3] 11812 K진 트리 - Java

문제링크 : https://www.acmicpc.net/problem/11812

11812번: K진 트리

 

접근 과정 : 

• 트리에서 부모 인덱스로 자식 인덱스를 계산하고, 자식 인덱스로 부모 인덱스를 계산하는 방식을 사용했다.
• 흔히 이진트리에서는 자식/2가 부모 인덱스가 되는 것처럼 이를 이용해 계산하려고 했다.
• 자식 인덱스를 보고 부모의 인덱스를 계산할 수 있는 방식이 필요했다.
• 나는 여려 계산 끝에, 부모 = (자식+K-2)/K 라는 식을 얻었고 이를 이용했다.

 

소스 코드 및 결과 :

package BOJ;


/* 
    K진 트리 
*/

import java.io.*;
import java.util.*;

public class BOJ11812 {
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long N = Long.parseLong(st.nextToken());
        long K = Long.parseLong(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());

            if (K == 1) {
                sb.append(Math.abs(x-y)).append("\n");
            }else{

                int d = 0;

                while (x != y) {
                    if (x > y) {
                        x = (x+K-2)/K;
                    }else{
                        y = (y+K-2)/K;
                    }

                    d++;
                }

                sb.append(d).append("\n");
            }
        }

        System.out.println(sb.toString().trim());

        
    }
}

 

P.S 

항상 겪는 것이지만, 트리를 활용하는 문제는 어려운 것 같다.