문제

1로 만들기

풀이

아직 다이나믹 프로그래밍에 입문중이라 이 문제를 봤을때 그냥 무난 if-else 설탕 문제인가 생각했는데 아니었다
점화식을 작성해야하는 DP는 이전값과 현재 값과의 인과관계를 생각해야 하는 문제들이 많은것 같다
내가 참고한 풀이는 이곳에서 참고 하였는데 cpp 코드이긴하지만 코드가 아주 단순하기 때문에 참고할 만 하다

		int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        System.out.println(dp[n]);

기본적으로 +1을 해주면서 값을 갱신해주는데 대신에
기본적으로 2, 3의 배수인경우는 몫의 +1을 해주면 현재 값의 연산방법을 출력할 수 있다
현재 값이 8인경우 dp[8/3] = dp[2] + 1 가 연산 횟수 가 된다
연산횟수가 이전 숫자의 연관관계를 바르게 파악하는 것이 중요한 것 같다.

전체 코드

전체 코드