[Algorithm] Programmers_숫자 변환하기 in Java

💡 Programmers Lv2. 숫자 변환하기:

DP를 활용하여 x를 y로 변환하는 최소 연산 횟수 찾기

🌱 코드 in Java

알고리즘: Dynamic programing

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int z = y + 1; // 배열 인덱스 및 불가능값을 위한 임시 변수
        int dp[] = new int[z]; // dp 배열 생성
        Arrays.fill(dp, z); // 불가능값으로 초기화
        dp[x] = 0; // x는 0번째 단계
        for (int i = x; i < z; i++) {
            if (dp[i] == z) // 조합이 아예 불가능한 숫자의 경우 건너뛰기 
                continue;
            if (i * 2 < z) // 인덱스 접근이 가능한 경우에
                dp[i * 2] = Math.min(dp[i] + 1, dp[i * 2]); // 전단계를 거쳐오는 경우와, 현재 단계에 저장되어있는 값을 비교하여 갱신
            if (i * 3 < z)
                dp[i * 3] = Math.min(dp[i] + 1, dp[i * 3]);
            if (i + n < z)
                dp[i + n] = Math.min(dp[i] + 1, dp[i + n]);
        }
        return dp[y] != z ? dp[y] : -1; // 갱신되었을 경우 그 최소값, 아닐 경우 -1 리턴
    }
}

이번 문제는 처음에 접근법을 못찾아서, 일단 dp로 풀 수 있다는 것을 알고 거기서부터 시작하였다.

dp라는 걸 알고 푸니 어떻게 풀어야 할지 감이 빠르게 왔는데,
문제를 보고 dp를 떠올리지 못하니 문제다.

좀 더 머리를 굴려보자.

🧠 기억하자

1. 단계를 거쳐가는 경우에 대부분 dfs 혹은 dp로 풀이가 가능한 때가 많은 것 같다.