[JAVA]백준_1463_1로만들기

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

1463번: 1로 만들기

 

문제 유형 : 다이나믹 프로그래밍

 

풀이 방식 : 다이나믹 프로그래밍이라고 적혀있었지만 간단한 BFS로 구현으로 풀었습니다

               문제에서 주어진 연산 3가지를 조건으로 큐에 넣었슴돠 

 

소스코드

 

package BOJ;

import java.io.*;
import java.util.*;

public class BOJ_1463_1로만들기_Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		int res = 0;
loop:	while(!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int now = q.poll();
				if(now==1) break loop;
				
				if(now%3==0) {
					q.offer(now/3);
				}
				if(now%2==0) {
					q.offer(now/2);
				}
				q.offer(now-1);
			}
			res++;
		}
		System.out.println(res);
	}

}