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

문제

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

프로그래머스

 

---

해설

특정 자연수 x에서 y로 변환하는데 필요한 최소 연산 횟수를 구하는 문제입니다.

bruteforce로 해결하려 한다면 각 연산요소 3가지(+n, *2, *3)을 매번 계산해 주어야 해서 x가 1이고 y가 1,000,000인 경우 3^1000000정도가 필요합니다. 하지만 DP를 사용하면 3*1000000정도로 깔끔한 풀이가 가능해 집니다.

 

목표는 최소 연산 횟수를 구하는 것이기 때문에 dp[i]는 i로 변환하는데 필요한 최소 연산 횟수라 설정합니다.

dp는 이전 값에서 영향을 받아 다음 값이 결정되기에 dp[i]는 i+n, i*2, i*3 이 3가지 요소에 영향을 줍니다. 예를 들어 *3 연산인 경우만을 가지고 진행해 보겠습니다.

dp[i*3] = dp[i]+1;

이때 dp[i*3](원래있던 값)이 dp[i]+1(새로 들어온 값)보다 더 작았을 수 있습니다, 최소 연산 횟수를 유지하기 위해 min을 사용합니다.

dp[i*3] = Math.min(dp[i]+1, dp[i*3]);

 이때 배열dp는 0으로 초기화되어 있기 때문에 min을 사용하면 0으로 계속 유지될 수 있으므로 처음 방문한 경우(0인 경우)에는 항상 dp[i]+1로 되도록 지정합니다.

dp[i*3] = dp[i*3] == 0 ? dp[i]+1 : Math.min(dp[i]+1, dp[i*3]);

또한 i*3은 for문에 의해 dp배열의 범위를 벗어날 수 있으므로 목표숫자(y)를 넘어간 경우는 연산하지 않도록 합니다.

if(i*3 <= y) dp[i*3] = dp[i*3] == 0 ? dp[i]+1 : Math.min(dp[i]+1, dp[i*3]);

이 점화식을 모든 연산들에게 적용시켜 줍니다. for문을 통해 x부터 y까지 모든 값들에 대해 연산을 하도록 합니다.

for(int i=x;i<=y;i++){
    if(i*3<=y) dp[i*3] = dp[i*3]==0 ? dp[i]+1 : Math.min(dp[i*3], dp[i]+1);
    if(i*2<=y) dp[i*2] = dp[i*2]==0 ? dp[i]+1 : Math.min(dp[i*2], dp[i]+1);
    if(i+n<=y) dp[i+n] = dp[i+n]==0 ? dp[i]+1 : Math.min(dp[i+n], dp[i]+1);
}

이렇게 둔다면 시작 숫자 x에서 연산을 통해 변환되는 숫자들은 1이상의 숫자가 되고 변환이 불가능한 숫자라면 0이 될것입니다. 하지만 x가 y일 경우와 y에 도달하지 못하는 경우가 구분없이 0이 되어 도달하지 못하는 경우는 -1로 변경이 필요합니다.

for(int i=x;i<=y;i++){
    if(i!=x && dp[i]==0) dp[i]=-1;
    else{
        if(i*3<=y) dp[i*3] = dp[i*3]==0 ? dp[i]+1 : Math.min(dp[i*3], dp[i]+1);
        if(i*2<=y) dp[i*2] = dp[i*2]==0 ? dp[i]+1 : Math.min(dp[i*2], dp[i]+1);
        if(i+n<=y) dp[i+n] = dp[i+n]==0 ? dp[i]+1 : Math.min(dp[i+n], dp[i]+1);
    }
}

y가 x인 경우는 제외되며 이전 단계에서 도달하지 못한 경우(dp[i]==0)는 -1로 변경해 줍니다. 이 경우는 도달하지 못한 경우이기 때문에 앞서 표현한 점화식에 연산되지 않게 하여 이후의 다른 dp들에게 영향을 주지 않도록 합니다.

 

주의점

• x가 y인 경우
• 도달하지 못한다면 -1로 출력

---

코드

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];

        for(int i=x;i<=y;i++){
            if(i!=x && dp[i]==0) dp[i]=-1;
            else{
                if(i*3<=y) dp[i*3] = dp[i*3]==0 ? dp[i]+1 : Math.min(dp[i*3], dp[i]+1);
            
                if(i*2<=y) dp[i*2] = dp[i*2]==0 ? dp[i]+1 : Math.min(dp[i*2], dp[i]+1);
            
                if(i+n<=y) dp[i+n] = dp[i+n]==0 ? dp[i]+1 : Math.min(dp[i+n], dp[i]+1);
            }

        }
        return dp[y];
    }
}