숫자 변환하기

링크텍스트

문제 설명

1. x에는 +n, x2, x3의 연산만을 수행할 수 있다.
2. y가 될 수 있는 최소 연산 횟수를 구하라.

시행 착오 및 풀이 방법

처음에는 while문으로 풀려고 했다.
근데 생각해보니 while문으로 풀면 횟수를 세지 못하는....
암튼 막혀서 코드 싹 지웠다.

2번째로 풀었을때는 DP를 사용하여 풀었다.

DP(동적 계획법, Dynamic Programming)

: 큰 문제를 작은 문제로 나누어 푸는 알고리즘
이미 해결한 작은 문제들의 결과를 저장하여 중복 계산을 방지하고 효율적으로 최적해를 구할 수 있다.

1. 큰 문제를 작은 문제로 나누어 해결할 수 있는가?
   ㄴyes!
   y의 값에 도달하기 위해 앞선 계산의 결과들을 점진적으로 쌓아간다.

2. 중복 계산을 줄일 수 있나?
   ㄴyes!
   이미 최소 횟수가 계산된 앞선 값을 활용한다.

이러한 이유로 dp 풀이를 진행하였다~
(사실은 이렇게까지 깊게 생각 안하고 음.. 쪼개서 쌓아갈 수 있겠군.... 아 dp?! 이렇게 풀었음)

정답 풀이

1. y+1의 크기의 배열을 만들어 -1로 채운다.
2. 시작(x)을 0으로 초기화 한다.
3. for문에서 i는 시작(x)부터 끝(y)까지 반복한다.
4. 주어진 연산으로 도달할 수 없는 숫자이면 continue;
5. +n, x2, x3 의 연산값이 y보다 작다면 배열에 해당 연산값까지 갈 수 있는 최소 횟수를 저장한다.
   5-1. 이때, 이미 도달해있는 숫자라면 해당 숫자까지 갈 수 있는 최소 횟수를 배열에 저장한다.
6. 배열에서 y값을 return한다. 이때, 배열[y]는 y까지 갈 수 있는 최소 횟수가 저장되어 있다.

정답 코드

//dp 풀이
import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        int[] dp = new int[y+1];
        Arrays.fill(dp,-1);
        
        //시작
        dp[x] = 0;
        
        for(int i=x; i<=y; i++) {
            //도달할 수 없는 숫자면 패스
            if(dp[i] == -1) {
                continue;
            }
        
            //+n
            if(i+n <= y) {
                //아직 도달하지 않은 숫자라면
                if(dp[i+n] == -1) {
                    dp[i+n] = dp[i]+1;
                }
                //이미 도달해있는 숫자라면 최솟값
                else {
                    dp[i+n] = Math.min(dp[i+n], dp[i]+1);
                }
            }
            
            //*2
            if(i*2 <= y) {
                if(dp[i*2] == -1) {
                    dp[i*2] = dp[i]+1;
                }
                else {
                    dp[i*2] = Math.min(dp[i*2], dp[i]+1);
                }
            }
            
            //*3
            if(i*3 <= y) {
                if(dp[i*3] == -1) {
                    dp[i*3] = dp[i]+1;
                }
                else {
                    dp[i*3] = Math.min(dp[i*3], dp[i]+1);
                }
            }
        }
        
        return dp[y];
    }
}

정답~

---

보자마자 dp가 떠오르거나 풀이 방법이 떠올랐어야 했는데..
많이 멀었다 멀었어