[백준 6615] 콜라츠 추측 (JAVA)

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

6615번: 콜라츠 추측

 

 

ICPC에서 출제됐던 흥미로운 문제를 다뤄보도록 하겠다.

 

문제에서 나와있는 콜라츠 추측은 다음과 같다.

 

1. 임의의 숫자 i가 짝수인경우,  i / 2
2. 홀수인 경우 i * 3 + 1을 반복한다.
3. 이 수열의 반복 결과는 1이된다.

 

문제에선 이 콜라츠추측이 옳다고 가정하에

두개의 정수를 주고 이 정수두개가 같은수가 되는 시점을 찾아

각각 몇번의 반복을 통해 같은수가 되는지 출력해주면 된다.

 

이 과정을 트리로 표현한다면,

루트가 1인 트리로 표현이 가능하다. 

(물론 4 >>2 >> 1 의 반복과정일때를 제외하는 경우에 그렇다. 문제에서도 이 부분에 대해선 언급하고 있다.)

 

이를 트리로 표현한다면 다음과 같은 불균형 이진트리로 나타난다.

 

 

이 트리의 특징은 각각의 노드가 유일한 키가 되며 콜라츠 추측으로 나오는

수열의 공통된 부분을 빠르게 찾아 낼 수 있단 점이다.

 

각각의 노드가 유일한 데이터를 갖기 때문에 두개의 콜라츠 추측으로 이루어진 수열을 갖는다 가정하면,

 

두 수열에서 일치하는 부분이 나오는 순간부터는 모두 동일한 값을 갖게된다

즉 트리의 공통조상을 갖는다는것을 알 수 있다.

 

가령 숫자 64와 3이 주어져 이 두 숫자로 각각 수열을 갖는다 가정할때

 

 

 

16이란 수를 갖는 부분에서 공통조상을 갖는것을 알 수 있다.

 

즉 수열로 표현 하자면

64  , 32 , 16  , 8 , 4 , 2 , 1

3, 10 , 5 , 16 ,  8 , 4 , 2 , 1

 

위와 같다는 것이다.

 

따라서 이 문제를 풀기 위한 아이디어는 각각의 노드가 유일한 데이터를 갖는다는 점

즉 map을 사용한다면 간단히 해결이 가능하다.

 

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

 

먼저 각 노드의 유일한 데이터와 그리고 깊이를 저장할 map을 하나 선언해주도록 하겠다.

그리고 변수로 몇번째에 일치하는 수인지, 그리고 해당 수에 대해서도 선언해준다.

 

	static HashMap<Long,Integer> map = new HashMap<>();
	static StringBuilder sb = new StringBuilder();
	
	static int stepA, stepB;
	static long c;

 

이제 순차적으로 수열의 진행에 따라 map에 저장하거나 이미 저장된 값이라면,

리턴해줄수 있도록 메소드를 작성해주면 된다.

 

	private static void setStep(long a) {
		int step = 0;
		while(true) {
			Integer val = map.put(a, step);
			if(val != null) { // 이전에 입력된적 있는 키인 경우
				stepA = val;
				stepB = step;
				c = a;
				return;
			}
			if(a == 1) return; // 1이면 리턴
			a = (a % 2 == 0) ? a / 2 : a * 3 + 1;
			step++;
		}
	}

 

이때 map의 put 메소드의 리턴값은 이미 key가 존재한다면 해당 value를 아니라면 null을 리턴한다는것을

이용할수 있다.

 

이전에 맵이 초기화된 상태라면 모든 수열이 진행되고 1일때 리턴되고

아닌 경우 수열의 진행중 공통조상을 만났을 경우 리턴되어 현재까지의 반복횟수, 그리고 이전수의 반복수,

그리고 현재 수에 대해 변수에 저장후 리턴될 것이다.

 

그리고 여러번의 테스트 케이스를 갖는다 했으므로 각 테스트 케이스마다 맵을 초기화 후

정수 두개를 각각 메소드에 인자로 주어 저장된 변수의 값으로 출력형식을 맞춰주는 메소드를 작성해준다.

 

	static void setSB(long a, long b) {
		map.clear();
		setStep(a);
		setStep(b);
		sb.append(a).append(" needs ").append(stepA)
		.append(" steps, ").append(b).append(" needs ")
		.append(stepB).append(" steps, they meet at ")
		.append(c).append('\n');
	}

 

 

코드를 실행해보면 정확한 답을 내는것을 알 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj6615 {
	
	static HashMap<Long,Integer> map = new HashMap<>();
	static StringBuilder sb = new StringBuilder();
	
	static int stepA, stepB;
	static long c;
	
	private static void setStep(long a) {
		int step = 0;
		while(true) {
			Integer val = map.put(a, step);
			if(val != null) { // 이전에 입력된적 있는 키인 경우
				stepA = val;
				stepB = step;
				c = a;
				return;
			}
			if(a == 1) return; // 1이면 리턴
			a = (a % 2 == 0) ? a / 2 : a * 3 + 1;
			step++;
		}
	}
	
	static void setSB(long a, long b) {
		map.clear();
		setStep(a);
		setStep(b);
		sb.append(a).append(" needs ").append(stepA)
		.append(" steps, ").append(b).append(" needs ")
		.append(stepB).append(" steps, they meet at ")
		.append(c).append('\n');
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		long a,b;
		while(true) {
			st = new StringTokenizer(in.readLine()," ");
			a = Long.parseLong(st.nextToken());
			b = Long.parseLong(st.nextToken());
			if(a == 0) break;
			setSB(a,b);
		}
		
		in.close();
		
		System.out.print(sb);
	}
	

}