백준 12852 - 1로 만들기 2

접근

0.5초라는 짧은 시간과 큰 입력, 같은 값이 여러번 나올 수 있는 특징으로 인해 다이나믹 프로그래밍이라는 생각을 할 수 있다.

문제 풀이

visited를 통해 해당 수가 나온 적 있는지, 그 때의 연산 횟수는 몇 번인지 알아야 한다. 또한, 정답 출력(연산이 진행되는 과정 순서대로)을 위해 해당 수가 나오기 전 수가 무엇인지 또한 저장해야 한다.
따라서 visited와 정답 출력을 위한 이전 수를 묶어서 처리하기로 했고, 연산 횟수는 레벨별 큐 탐색을 통해 따로 저장하지 않고 처리하기로 했다.

처음 입력받은 수부터 순서대로 세 가지 연산을 진행한 후, 연산 진행 후 숫자의 인덱스에 연산 진행 전 숫자를 저장해 해당 숫자가 탐색한적 있는지 확인한다.

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        
        //만약 1을 입력받았을 시, 예외처리를 한 후 종료
		if(n == 1) {
			System.out.println(0);
			System.out.println(1);
			return;
		}
		int[] back = new int[n + 1];
		
		int cnt, size, last = -1;
        //현재 연산해야하는 수를 알기 위해  Queue 사용
        //처음 입력받은 수, n부터 Queue에 넣어 저장
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(n);

		//연산 횟수별로 나눠서 Queue에서 수를 하나씩 꺼내 탐색
		cnt = 0;
		while (!que.isEmpty()) {
			size = que.size();
			cnt++;
            
            //Queue에서 수를 하나씩 꺼내서 세가지 연산 진행
            //만약 탐색되지 않은 수일 시, 저장 후 큐에 넣음
			for (int i = 0; i < size; i++) {
				n = que.poll();
				
				if (n % 3 == 0 && back[n / 3] == 0) {
					back[n / 3] = n;
					que.add(n / 3);
				}
                
				if (n % 2 == 0 && back[n / 2] == 0) {
					back[n / 2] = n;
					que.add(n / 2);
				}

				if (back[n - 1] == 0) {
					back[n -1] = n;
					que.add(n -1);
				}
				
				if(back[1] != 0) {
					break;
				}
			}
            
            //만약 연산 결과가 1이 나왔을 시, break
			if(back[1] != 0) {
				break;
			}
		}
        
        //연산 횟수를 출력
		System.out.println(cnt);
		n = 1;
        //스트링 빌더를 통해 처리했지만,
        //stack을 통해서 뒤에서부터 출력하도록 처리한 결과도 크게 다르지 않았다.
		StringBuilder sb = new StringBuilder();
		for(int i = -1; i < cnt; i++) {
			sb.insert(0, " ");
			sb.insert(0, n);
			n = back[n];
		}
		System.out.println(sb);
	}

}