숫자 변환하기(프로그래머스) JAVA

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

프로그래머스

 

• 40이 될려면 10에 2를 2번 곱한다.
• 40이 될려면 10에 30을 더한다.
• 2가 5가될 방법이 없다.

 

문제에 대한 아이디어 및 구현

문제를 보자마자 느낀점은 최적의 상황만 선택해서 구해줘야 할 것 같았다. 그래서 그리디를 사용해볼까 였다. 하지만 생각해야할 조건이 너무 많아진다는 느낌을 받았다. 지금까지 문제를 풀면서 그리디로 풀면 좋을거 같은데 생각해야할 조건이 너무 많을 때는 DP를 사용하는 문제였다. DP를 사용해서 앞에서 구한 답을 이용해 모든 부분을 조사해보면 대부분 해결 되는 것 같다.

 

첫번째 방법

• now * 2인 지점, now * 3인 지점, now + n인 지점 3곳을 조사해서 dp[now] + 1이랑 dp[next] 중 더 작은 것을 고르는 것이다.

while(!dq.isEmpty()){
            int now = dq.removeFirst();
            if(now*2 <= y ){
                dp[now*2] = Math.min(dp[now*2], dp[now]+1);
                dq.addLast(now*2);
            }
            if(now*3 <= y){
                dp[now*3] = Math.min(dp[now*3], dp[now]+1);
                dq.addLast(now*3);
            }
            if(now+n <= y){
                dp[now+n] = Math.min(dp[now+n], dp[now]+1);
                dq.addLast(now+n);
            }
        }

당연히 통과일줄 알았지만 시간초과 였다.

왜 시간초과일까?
이렇게 할 경우 한번 들린 곳도 계속 접근을 하게 된다. 
예를 들어 dp[20]인 곳을 제일 처음 방문했을 때는 10 * 2일 때이다. 하지만 10 + 5 +5 를 했을 때도 dp[20]을 또 방문한다. 그러므로 한번 방문 한 곳은 방문하지 않게 해야 한다.

 

두번째 방법

while(!dq.isEmpty()){
            int now = dq.removeFirst();
            if(now*2 <= y && dp[now*2] == 0){
                dp[now*2] = dp[now]+1;
                dq.addLast(now*2);
            }
            if(now*3 <= y && dp[now*3] == 0){
                 dp[now*3] = dp[now]+1;
                dq.addLast(now*3);
            }
            if(now+n <= y && dp[now+n] == 0){
                dp[now+n] = dp[now]+1;
                dq.addLast(now+n);
            }
}

다음 방문 할 곳이 0인 곳만 방문하게 했다. 그러면 최소값을 선택할 필요도 없고 그냥 현재에 + 1을 하면 된다. 제일 처음 방문했을 때가 가장 최소만에 접근한 것이기 때문이다.

결과는 테스트 6만 실패!!!

도저히 모르겠어서 질문하기를 봤더니 제일 처음부터 x와 y가 같을 수 있다고 한다.

if(x==y) return 0;

이걸 추가해 줘야 한다.

 

전체 코드

import java.util.*;

class Solution {
  
    public int solution(int x, int y, int n) {
        int answer = 0;
        int dp[] = new int[y+1];
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addFirst(x);
        if(x==y) return 0;
        while(!dq.isEmpty()){
            int now = dq.removeFirst();
            if(now*2 <= y && dp[now*2] == 0){
                dp[now*2] = dp[now]+1;
                dq.addLast(now*2);
            }
            if(now*3 <= y && dp[now*3] == 0){
                 dp[now*3] = dp[now]+1;
                dq.addLast(now*3);
            }
            if(now+n <= y && dp[now+n] == 0){
                dp[now+n] = dp[now]+1;
                dq.addLast(now+n);
            }
        }
        if(dp[y] == 0){
            answer = -1;
        }
        else answer = dp[y];
        return answer;
    }
    
}