백준 무한 유리수 트리(10436)

무한 유리수 트리

1. 힌트

1) 루트가 $1/1$이므로 자식들은 이보다 증가하기만 합니다. 따라서 이진 트리에서 왼쪽 자식이면 $p/q$에서 $q$가 무조건 큽니다. 오른쪽 자식도 마찬가지로 $p/q$에서 $p$가 무조건 큽니다.

2) 왼쪽 자식이라면 중위 순회의 다음 노드는 부모에게 올라갔다가 다시 오른쪽 자식으로 내려가는 것입니다.

3) 가장 오른쪽 노드가 아니고, 오른쪽 자식이라면 $F(n)$에서 $F(n+1)$으로 이동해야 합니다. $F(n)$이 포함된 서브트리를 왼쪽 자식으로 가지고 $F(n + 1)$이 포함된 서브트리를 오른쪽 자식으로 가지는 서브트리가 반드시 존재합니다. 이 서브트리의 루트를 지나서 찾아갑시다.

2. 접근

1) 이진 트리

이진 트리는 왼쪽 자식과 오른쪽 자식이 존재합니다. 그림을 그려서 생각해 보면, 왼쪽 자식인 경우는 그 다음 중위 순회로 찾는 원소는 위 레벨로 올라갔다가 오른쪽 자식으로 내려오는 것임을 알 수 있습니다.

오른쪽 자식인 경우는 이진 트리의 맨 오른쪽에 있는 경우를 제외하면 부모 노드로 쭉 올라갔다가 다시 오른쪽 자식을 타고 내려오면 다음 중위 순회로 찾는 원소를 찾아갈 수 있습니다. $F(n)$과 $F(n+1)$사이의 경로에서 반드시 어떤 서브트리의 루트를 지나게 되는데 이 때, 만나는 노드들에는 규칙이 있습니다. 어떤 노드가 왼쪽 자식이면 $l$, 오른쪽 자식이면 $r$이라고 할때 $r,\ r,\ ...,\ l,\ mid,\ r,\ ...,\ \ l,\ l$과 같은 양상을 띕니다. 즉 오른쪽 자식이다가 왼쪽 자식으로 바뀌는 때가 반드시 있습니다. 또한 이 노드들의 나열은 좌우 대칭입니다.

왼쪽 자식은 반드시 분모다 더 크므로 분모가 더 커질 때 까지 왼쪽 위로 올라가는 연산을 해주고, 그 해준 횟수만큼 다시 내려가는 연산을 해주면 $F(n)$에서 $F(n + 1)$로 도달할 수 있습니다. 이러한 과정은 올림하는 나눗셈 연산으로 구현할 수 있습니다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " |/");
			st.nextToken();
			long p = Long.parseLong(st.nextToken());
			long q = Long.parseLong(st.nextToken());
			if (p == 1 && q == 1) {
				p = 1; q = 2;
			} else if (q == 1) {
				q = p + 1; p = 1;
			} else if (p > q) {
				long cnt = (p - 1) / q;
				p -= q * cnt;
				q -= p;
				p += q;
				q += p * cnt;
			} else {
				long t = p;
				p = q;
				q -= t;
			}
			bw.append(tc).append(" ").append(p).append("/").append(q).append("\n");
		}
		System.out.print(bw);
	}

}