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

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

프로그래머스

 

문제풀이

dp를 통해 각 값에 따른 최소 연산 갯수를 저장한다.

저장하는 방법은 각각의 연산에 따라서 기존 값의 연산 횟수 vs 연산 이전의 수행 횟수 + 1 (연산 수행)

말로하면 더 헷갈리니 코드로 보자

 

코드

import java.util.*;
class Solution {
    static int[] dp;
    static final int INF=1000001;
    public int solution(int x, int y, int n) {
        dp = new int[y+1];
        Arrays.fill(dp, INF);
        
        dp[x]=0;
        for(int i=x; i<=y; i++){
            if (i+n<=y)
                dp[i+n]=Math.min(dp[i+n], dp[i]+1);
            if (i*2<=y)
                dp[i*2]=Math.min(dp[i*2], dp[i]+1);
            if (i*3<=y)
                dp[i*3]=Math.min(dp[i*3], dp[i]+1);
        }
        return (dp[y]==INF?-1:dp[y]);
    }
}

각각의 if문에서 기존 값의 연산 횟수 vs 이전 값에 연산을 수행한 횟수를 비교하며 y값까지 진행한다.

 

주의할 점

최솟값을 구하기 때문에 min을 사용하는데 이때 무한값으로 사용한다고 INTEGER.MAX_VAULE를 사용하면 몇몇 테스트 케이스에 실패한다. dp[i]+1에서 오버플로우가 발생하기 때문에 y값의 범위보다 큰 수이지만 INTEGER.MAX_VAULE보단 적어도 1은 작아야 한다.