[Programmers] 숫자 변환하기 / ⭕

프로그래머스

 

1. 제출 코드 (16분 07초 / DP)

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[1000001];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[x] = 0;

        for(int i = x; i < y; i++) {
            if(dp[i] != Integer.MAX_VALUE) {
                if(i + n <= 1000000) {
                    dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
                }
                if(i * 2 <= 1000000) {
                    dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
                }
                if(i * 3 <= 1000000) {
                    dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
                }
            }
        }
        if(dp[y] != Integer.MAX_VALUE) {
            answer = dp[y];
        } else {
            answer = -1;
        }
    
        return answer;
    }
}

 

 

2. 구현 로직

1. y의 값이 최대가 1,000,000이므로 1,000,001 크기의 DP 배열 생성
2. DP 배열에는 연산 횟수가 담기기 때문에 각 배열의 값은 Integer.MAX_VALUE로 초기화
3. x부터 시작이므로 dp[x]=0으로 초기화
4. x부터 y까지 Integer.MAX_VALUE가 아닌 것을 하나씩 탐색
   1. i + n, i * 2, i * 3이 1,000,000보다 클 경우는 없기에 조건문 삽입
   2. dp[i]에 추가 연산 +1과 연산되어 나온 인덱스( i + n, i * 2, i * 3)의 Value와 비교하여 최솟값을 저장
5. 만약 dp[y]가 Integer.MAX_VALUE이면 나올 수 없는 값이므로 -1

 

3. 유의할 점

• y의 크기를 보지않고 dfs로 문제를 풀이를 하다가 다시 생각해보니 시간 초과가 날 거 같아 DP로 풀이를 진행했다.