SWEA 11688. Calkin-Wilf tree 1

Calkin-Wilf tree는 모든 양의 유리수를 정확히 하나씩 포함하고 있는 트리다. 이 트리는 다음과 같이 정의된다
    ∙ 트리의 루트는 1/1 을 나타낸다.
    ∙ 트리의 각 노드는 왼쪽 자식과 오른쪽 자식을 가지는데 어떤 노드가 a/b 를 나타내고 있다면, 왼쪽 자식은 a/a+b 를 오른쪽 자식은 a+b/b 를 나타낸다.
루트 노드에서부터, 자식을 따라 내려간 방향이 순서대로 주어질 때, 마지막에 위치한 노드가 어떤 유리수를 나타내는지 구하는 문제이다.

 

길이가 30 이하이므로 a, b를 조건에 맞게 더해주면서 누적하면 된다. 누적 종료 후, 기약분수로 나타내야 하며 이는 최대공약수로 a, b를 각각 나눈 결과를 띄어쓰기로 구분하여 출력하면 된다.

private static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int a = 1, b = 1;
for (int i = 0; i < line.length(); i++) {
    if (line.charAt(i) == 'L') b += a;
    else a += b;
}
int gcd = gcd(a, b);
sb.append(a/gcd).append(' ').append(b/gcd).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            String line = br.readLine();
            int a = 1, b = 1;
            for (int i = 0; i < line.length(); i++) {
                if (line.charAt(i) == 'L') b += a;
                else a += b;
            }
            int gcd = gcd(a, b);
            sb.append(a/gcd).append(' ').append(b/gcd).append('\n');
        }

        br.close();
        System.out.print(sb);
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}