[BOJ] 12852번 1로 만들기 2 - JAVA

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

12852번: 1로 만들기 2

 

이번 문제는 

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

1463번: 1로 만들기

이 문제의 진화된 버전이라고 생각한다.

1로 만들기의 경우 재귀와 dp를 같이 써서 풀었다. 최소 횟수만 나타나면 되는 문제라서 가능했는데 1로만들기 2 같은 경우 어떤 숫자들을 지나갔는지가 함께 출력이 되야해서 고민하는 시간을 가졌다.

처음에는 1로 만들기의 코드를 응용해서 문제를 풀려고 했다. 

import java.util.*;
public class Main {
	static int[] d = new int[1000001];
	public static void main(String[] args) {
		Main m = new Main();
		Scanner sc = new Scanner(System.in);
		d[1] = 0;
		int n = sc.nextInt();
		
		int result = m.go(n);
		System.out.println(result);
		for(int i = n; i>0; i--){
			System.out.print(i+" ");
			if(i%2 == 0) i = d[i/2] == result - 1 ? i/2+1 : i;
			else if(i%3==0) i = d[i/3] == result - 1 ? i/3+1 : i;
			result -= 1;
		}
	}
	
	public int go(int n) {
		if(n == 1) return 0;
		if(d[n] > 0) return d[n];

		d[n] = go(n-1) + 1;
		
		if(n%2 == 0) {
			int temp = go(n/2)+1;
			if(d[n] > temp) d[n] = temp;
		}
		
		if(n%3 == 0) {
			int temp = go(n/3)+1;
			if(d[n] > temp) d[n] = temp;
		}
		
		return d[n];
	}

}

원래의 main 코드에서 for loop만 추가해줬다.

주어진 x값의 최대 횟수와 x가 될 수 있는 수의 경로 횟수 값이 -1 되는 것을 다음 i로 결정했다.

그러나 틀렸습니다라는 문구가 떠서 바로 포기하고 BFS로 다시 풀어보았다.

밑의 코드는 다시 풀어본 코드이다.

import java.util.*;
public class Main {
	static int[] d = new int[1000001];
	static int[] node = new int[1000001];
	static boolean[] check = new boolean[1000001];
	public static void main(String[] args) {
		Main m = new Main();
		Scanner sc = new Scanner(System.in);
		d[1] = 0;
		int n = sc.nextInt();
		check[n] = true;
		Queue<Integer> q = new LinkedList<>();
		q.add(n);
		while(!q.isEmpty()){
			int a = q.poll();
			if(a < 1) continue;
			if(d[a-1] == 0){
				q.add(a-1);
				d[a-1] = d[a]+1;
				node[a-1] = a;
			}
			if(a%2 == 0){
				if(d[a/2] == 0){
					q.add(a/2);
					d[a/2] = d[a]+1;
					node[a/2] = a;
				}
			}
			if(a%3 == 0){
				if(d[a/3] == 0) {
					q.add(a/3);
					d[a/3] = d[a]+1;
					node[a/3] = a;
				}
			}
		}
		System.out.println(d[1]);
		go(1);
		for(int i = n; i>0; i--){
			if(check[i]) System.out.print(i+" ");
		}
	}
	static public void go(int i){
		if(node[i] == 0) return;
		check[i] = true;
		go(node[i]);
	}
}

BFS풀었더니 맞았다.

근데 마음에 들지는 않는다.. 뭔가 더 깔끔하게 풀 수 있을것 같은데 아쉽다.

입력받은 N을 세가지의 경우의 수로 Queue에 넣어 문제를 이어갔다. 

1이 되면 continue로 지나가 q를 비우게 만든 뒤 가장 먼저 도착한 1번 경로를 boolean값으로 체크해 출력했다.