백준알고리즘 1463번 1로 만들기

문제링크

세준이는 어떤 정수 N에 다음과 같은 연산중 하나를 할 수 있다.

1. N이 3으로 나누어 떨어지면, 3으로 나눈다.
2. N이 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

세준이는 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.

다이나믹 프로그래밍을 이용한 기법이다.
다이나믹 프로그래밍은 재귀 함수를 호출하여 풀 경우가 많다고 하였고, 재귀함수는 스택구조로 이루어져 있어 호출한 함수의 순서를 유의하면 문제 푸는데 많은 도움이 된다고 한다. (사실.... 재귀 함수 호출 순서를 이해하는데 많이 어렵다.. 휴..... 공부를 하자 ..)

기저 사례는 value 가 1 일 경우와 2 또는 3 으로 나누어 졌을 때 if문안의 내용을 주의 하면 풀 수 있다.
한번 푼 문젠데 진짜 오래걸렸다.
반성한다...

정답

import java.util.Scanner;

//1로 만들기 

public class Main {
    public static int[] d;

    public static int go(int n) {
        if (n == 1) {
            return 0;
        }

        d[n] = go(n - 1) + 1;

        if (n % 2 == 0) {
            int temp = d[n / 2];
            if (temp < d[n]) {
                d[n] = temp + 1;
            }
        }

        if (n % 3 == 0) {
            int temp = d[n / 3];
            if (temp < d[n]) {
                d[n] = temp + 1;
            }
        }

        return d[n];
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n + 1];
        System.out.println(go(n));
    }
}