Lv.2 숫자 변환하기 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(12분 21초)

아이디어

전형적인 DP 문제이다.
배열 arr을 1,000,001 크기로 생성하고 전부 -1로 초기화한다.
시작값인 x에는 연산 횟수 0을 저장한다.

그 후 1부터 y까지 반복하면서, 현재 위치 i에 도달할 수 있는 세 가지 경우를 고려한다:

• i - n이 0보다 크고 arr[i - n] != -1일 경우
• i가 2의 배수이고 arr[i / 2] != -1일 경우
• i가 3의 배수이고 arr[i / 3] != -1일 경우

이전 위치의 연산 횟수 +1 값을 우선순위 큐에 넣고, 그 중 최소값을 arr[i]에 저장한다.
이 과정을 통해 arr[y]에는 x에서 y로 도달하는 최소 연산 횟수가 저장된다.

정답 코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int[] arr = new int[1000001];
        Arrays.fill(arr, -1);
        arr[x] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 1; i <= y; i++) {
            if (i - n > 0 && arr[i - n] != -1) {
                pq.add(arr[i - n] + 1);
            }
            if (i % 2 == 0 && arr[i / 2] != -1) {
                pq.add(arr[i / 2] + 1);
            }
            if (i % 3 == 0 && arr[i / 3] != -1) {
                pq.add(arr[i / 3] + 1);
            }
            if (!pq.isEmpty()) {
                arr[i] = pq.poll();
            }
            pq.clear();
        }

        return arr[y];
    }
}