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

문제

설명

• dp 사용
• 배열 전체 최댓값으로 초기화
• 각 배열의 값에 x로 부터 현재 값이 만들어지는 연산의 최솟값을 갱신해 저장
• 이때, if(arr[i] == Integer.MAX_VALUE) continue; 를 넣지 않자 1, 8, 11, 12, 14, 15, 16번 테케가 틀렸다
• 찾아보니 예외처리를 하지 않으면 Integer.MAX_VALUE이 오버플로우가 발생해 값이 달라지는 것 같다고한다
  [참고] https://stritegdc.tistory.com/324

제출 코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;

        int[] arr = new int[y+1];
        // 전체 배열 최댓값으로 초기화
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[x] = 0;

        for(int i=x; i<y+1; i++){
            if(arr[i] == Integer.MAX_VALUE) continue;
            // n을 더했을 때
            if(i+n < y+1) arr[i+n] = Math.min(arr[i+n], arr[i]+1);
            // 2를 곱했을 때
            if(i*2 < y+1) arr[i*2] = Math.min(arr[i*2], arr[i]+1);
            // 3을 곱했을 때
            if(i*3 < y+1) arr[i*3] = Math.min(arr[i*3], arr[i]+1);
        }

        if(arr[y] == Integer.MAX_VALUE) answer = -1;
        else answer = arr[y];

        return answer;
    }
}