[JAVA] 숫자 변환하기 - 프로그래머스[Lv.2]

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

프로그래머스

---

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

💡 DP

풀이

• x = y 인 경우는 0으로 반환해야 한다...ㅎㅎ 생각 못해서 한~참 헤맴
• 아래 틀린 풀이에서 알 수있듯이, x에서 3가지 연산을 통해 나온 값만 고려해야함
  • 고로 x ~ y 까지 모든 값을 대상으로 cnt를 갱신하는게 아니라, x의 연산 결과인 값에 대해서만 갱신해야 함
  • cnt[i] 배열이 갱신 됐는지 판별 -> 갱신 됐어야 x 연산의 결과라는 거니까!
  • 이러니 패스했다.

# 1차 풀이

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

>> 이러면 2, 3, n 연산으로 도출 불가능한 숫자까지 연산에 포함됨 (테케 1번, 13번인가 거기부터 좌르륵 틀림)

>> 애초에 불가능한 값인지 판별해서 걸러주면 됨!