[BOJ] - 1로 만들기 / 1463번 (Java)

[BOJ] - 1로 만들기 / 1463번 (Java)

[BOJ] - 1로 만들기 / 1463번 (Java)

1. 문제 접근

N이 주어졌을 때, 1로 만들기 위한 연산의 최소 횟수를 구하면 된다.

 

연산을 1. 3으로 나누기, 2. 2로 나누기, 3. 1빼기 총 3가지가 존재한다.

 

해당 문제는 DP로 풀 수 있지만, 나의 경우에는 BFS를 통해 풀었다.

 

N을 시작점으로, 도달할 수 있는 번호를 `Queue`에 넣으면서 진행했다.

 

나누기 연산의 경우, 나누어 떨어질 경우만 고려했고, 공통적으로 기존의 거리(`dist`)와 비교하여 짧은 경우에 한하여 `Queue`에 삽입했다.

int currNum = q.poll();
if (currNum == GOAL)
    break;
if (currNum % 3 == 0 && dist[currNum] + 1 < dist[currNum / 3]) {
    // 3으로 나누어 떨어지고, 기존의 연산 횟수보다 작을 경우
    q.offer(currNum / 3);
    dist[currNum / 3] = dist[currNum] + 1;
}
if (currNum % 2 == 0 && dist[currNum] + 1 < dist[currNum / 2]) {
    // 2으로 나누어 떨어지고, 기존의 연산 횟수보다 작을 경우
    q.offer(currNum / 2);
    dist[currNum / 2] = dist[currNum] + 1;
}
if (dist[currNum] + 1 < dist[currNum - 1]) {
    // 기존의 연산 횟수보다 작을 경우
    q.offer(currNum - 1);
    dist[currNum - 1] = dist[currNum] + 1;
}

 

연산이 숫자를 증가시키는 연산이 없으므로, 방문 배열은 별도로 사용하지 않았다.

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * [BOJ] - 1로 만들기 / 1463번
 * @author JinHxxxxKim
 * 
 * 1. N번 부터 3으로 나누어 질 경우, 2로 나누어질 경우 분리해서 고려
 * 2. 나누어진다면, 기존의 최소 연산횟수와 비교하여 최소값으로 갱신
 * 3. 목표 지점(1)을 만나면 종료
 */
public class Sol_1463 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static final int GOAL = 1;
	private static int N;
	private static int[] dist;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine().trim());
		dist = new int[N + 1];
		Queue<Integer> q = new ArrayDeque<>();
		// 초기 연산 횟수 초기화
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[N] = 0;
		q.add(N);
		while (!q.isEmpty()) {
			int currNum = q.poll();
			if (currNum == GOAL)
				break;
			if (currNum % 3 == 0 && dist[currNum] + 1 < dist[currNum / 3]) {
				// 3으로 나누어 떨어지고, 기존의 연산 횟수보다 작을 경우
				q.offer(currNum / 3);
				dist[currNum / 3] = dist[currNum] + 1;
			}
			if (currNum % 2 == 0 && dist[currNum] + 1 < dist[currNum / 2]) {
				// 2으로 나누어 떨어지고, 기존의 연산 횟수보다 작을 경우
				q.offer(currNum / 2);
				dist[currNum / 2] = dist[currNum] + 1;
			}
			if (dist[currNum] + 1 < dist[currNum - 1]) {
				// 기존의 연산 횟수보다 작을 경우
				q.offer(currNum - 1);
				dist[currNum - 1] = dist[currNum] + 1;
			}
		}
		System.out.println(dist[GOAL]);
	}
}

---

3. 디버깅

`Queue`에 삽입할 때, 기존의 연산 횟수보다 작아지는 경우에만 삽입함으로 조금 더 최적화 시킬 수 있었다.

---

4. 결과