[백준 BOJ/Silver III] 1463번 : 1로 만들기

 

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

1463번: 1로 만들기

 

가능한 경우들을 확인하며 1을 만났을때 이동한 최소의 수(num[1]-1)를 최종 답으로 출력하면 된다

 

최종 코드

package boj1463;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	
	static int N;
	static int[] num;
	static Deque<Integer> dq = new ArrayDeque<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		num = new int[N+1];
		num[N] = 1;
		dq.addLast(N);
	
		bfs();
		System.out.println(num[1]-1);
	}
	
	static void bfs() {
		
		while(!dq.isEmpty()) {
			
			int x = dq.pollFirst();
			
			if(x % 3 == 0) {
				int nx = x / 3;
				if(num[nx] == 0) {
					num[nx] = num[x] + 1;
					dq.addLast(nx);
				}
			}
			
			if(x % 2 == 0) {
				int nx = x / 2;
				if(num[nx] == 0) {
					num[nx] = num[x] + 1;
					dq.addLast(nx);
				}
			}
			
			if(x-1 >= 1) {
				int nx = x - 1;
				if(num[nx] == 0) {
					num[nx] = num[x] + 1;
					dq.addLast(nx);
				}
			}

			if(num[1] != 0) return;
			
		}
	}
}