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

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

고찰 과정

간단하게 점화식을 세워서 문제를 해결할 수 있었습니다. 특정 지점 i까지의 최소 연산의 수를 d[i]로 정의하면 시작점 x부터 끝지점 y까지의 점화식은 다음과 같이 세울 수 있습니다.

1. 2를 곱해서 가는 경우
   -> d[i * 2] = min(d[i] + 1, d[i * 2])
2. 3을 곱해서 가는 경우
   -> d[i * 3] = min(d[i] + 1, d[i * 3])
3. n을 더해서 가는 경우
   -> d[i + n] = min(d[i] + 1, d[i + n])

이 때 초기의 d의 모든 값들은 무한이 큰 숫자로 초기화를 합니다. 이를 바탕으로 코드를 구현하면 됩니다.

 

---

코드

import java.util.*;

class Solution {
    
    private static final int INF = (int) 1e9;
    private static final int INVALID = -1;
    
    public int solution(int x, int y, int n) {
        int answer = INVALID;
        int[] d = new int[y + 1];
        Arrays.fill(d, INF);
        d[x] = 0;
        
        for (int i = x; i <= y; ++i) {
            if (d[i] == INF) {
                continue;
            }
            
            if (i * 2 <= y) {
                d[i * 2] = Math.min(d[i] + 1, d[i * 2]);
            }
            
            if (i * 3 <= y) {
                d[i * 3] = Math.min(d[i] + 1, d[i * 3]);
            }
            
            if (i + n <= y) {
                d[i + n] = Math.min(d[i] + 1, d[i + n]);
            }
        }
        
        if (d[y] != INF) {
            answer = d[y];
        }
        
        return answer;
    }
}