[프로그래머스] 숫자변환하기

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

	public class Programmers_숫자변환하기 {
	public static void main(String[] args) {
	System.out.println(new Programmers_숫자변환하기().solution(10, 40, 50)); // 2
	System.out.println();
	System.out.println(new Programmers_숫자변환하기().solution(10, 40, 30)); // 1
	System.out.println();
	System.out.println(new Programmers_숫자변환하기().solution(2, 5, 4)); // -1
	System.out.println();
	System.out.println(new Programmers_숫자변환하기().solution(10, 10, 50)); // 2
	System.out.println();
	}
	private int solution(int x, int y, int n){
	if (x == y) {
	return 0;
	}
	int[] arr = new int[10000001];
	Queue<Integer> q = new LinkedList<>();
	q.add(x);
	while(!q.isEmpty()){
	int num = q.poll();
	int[] temp = new int[3];
	temp[0] = num + n;
	temp[1] = num * 2;
	temp[2] = num * 3;
	for(int i=0; i<3; i++){
	int next = temp[i];
	if(next>y){
	continue;
	}
	if(arr[next] == 0 || arr[next] > arr[num]+1){
	arr[next] = arr[num]+1;
	q.add(next);
	}
	}
	}
	return arr[y] != 0 ? arr[y] : -1;
	}
	}

view raw Programmers_숫자변환하기.java hosted with ❤ by GitHub

---

 

BFS를 사용해서 풀이를 진행함

x + n

x * 2

x * 3

을 한 루프에서 진행해 조건에 맞고 (<=y), 최소한으로 이동하는 방법을 계산