[백준 13077] Sequence (JAVA)

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

13077번: Sequence

 

 

오늘 포스팅에서 다뤄볼 문제는 ICPC에서 출제된 트리문제이다.

 

문제 분석을 하자면,

 

루트는 1/1로 왼쪽수를 p 오른쪽수를 q라고 하고,

왼쪽 자식노드엔 p/p+q,

오른쪽 자식노드엔 p+q/q

를 갖도록 하는 이진트리의 구조를 갖는다.

 

그리고 여러번의 테스트케이스를 통해 각 노드가 몇번째로 생성되는 노드인지 출력하면되는것이다.

(이때 노드의 생성기준은 너비를 기준으로 한다.) 

 

가능한 범위내의 모든 노드를 저장해 답을 출력하기엔 시간초과나 메모리초과를 불러올듯 하므로

입력받은 테스트케이스를 역으로 연산해 답을 가져올수 있도록 하는것이 답이라고 생각했다.

 

트리를 다시 한번 살펴보면 각 노드를 p/q라고 한다면,

왼쪽자식노드가 되는 노드라면 p < q

오른쪽 자식노드가 되는 노드라면 p > q라는 규칙을 갖는다.

 

따라서 입력받은 데이터의 p,q값의 대소를 비교후 큰값에서 작은값을 빼기를 반복하며

왼쪽노드인지 오른쪽노드인지 기억하고,

루트에 도달하는 순간 다시 왼쪽노드인지 오른쪽노드인지 기억해둔값에 따라 원래값으로 트리를 타고 내려가며

몇번째 노드인지 찾아낼수 있다.

 

예제 5/2을 예로들자면,

 

 

다음 그림과 같은 과정을 거쳐 11번째 노드라는것을 알아 낼 수 있는것이다.

 

그럼 바로 코드로 풀이 해보도록 하겠다.

 

먼저 몇번째 노드인지 저장할 변수를 두도록하겠다.

 

	static int no;

 

그리고 오른쪽 노드인지 왼쪽노드인지 판단 후 연산해줄 메소드를 하나 선언한다.

 

이때 이 메소드는 재귀호출을 통해 method area의 구조인 stack 을 사용해

왼쪽 노드인지 오른쪽 노드인지 기억후 순차적으로 연산해줄수 있도록 하겠다.

이때 메소드의 리턴시점은 루트노드를 만나는 시점이 될 것이다.

 

	static void sequence(int p, int q) {
		if(p == 1 && q == 1) return;
		if(p > q) {
			sequence(p - q,q);
			no <<= 1;
			no++;
		}else {
			sequence(p,q - p);
			no <<= 1;
		}
	}

 

 

남은것은 테스트케이스를 순차적으로 받으며 노드번호를 초기화해주는 작업만 해주면 된다.

노드는 1번부터 시작하므로 각 테스트 케이스마다 1로 초기화 후 입력받은 데이터를 넣어주면 된다.

 

		while(t-- > 0) {
			no = 1;
			st = new StringTokenizer(in.readLine(),"/");
			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			sequence(p,q);
			sb.append(no).append('\n');
		}

 

 

예제를 실행시켜보면 정확한 답을 내는것을 볼 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj13077 {
	
	static int no;
	
	static void sequence(int p, int q) {
		if(p == 1 && q == 1) return;
		if(p > q) {
			sequence(p - q,q);
			no <<= 1;
			no++;
		}else {
			sequence(p,q - p);
			no <<= 1;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int t = Integer.parseInt(in.readLine());
		
		while(t-- > 0) {
			no = 1;
			st = new StringTokenizer(in.readLine(),"/");
			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			sequence(p,q);
			sb.append(no).append('\n');
		}
		
		in.close();
		
		System.out.print(sb);
	}
	

}