백준 알고리즘 1463번 동적계획법 기초

동적계획법(Dynamic Programming) 기초

이 문제도 Top-Down 방식을 통해 해결 하였는데... 내가 생각한 Top-Down이 이게 맞는지 모르겠다.

입력 받은 N을 기준으로

각각, 3으로 나누기, 2로 나누기, 1을 빼기

세 가지 방법을 시작으로 연산을 시작한다. 하나만 하는 것이 아니고

(3가지 방법을 모두 진행해 보고 그 중 최소값을 배열에 담아 두는 방식)

예를 들면 3을 1로 만드는 연산 방법은

3 / 3 = 1 의 방법과

(3 -1) / 2 의 방법이 있기 때문에

그 중 연산횟수가 최소가 되는 첫 번째 방법의 연산 횟수가 구하고자 하는 출력 값이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class num_1463
{
    static public void main(String args[]) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        int[] dp = new int[T+1];

        System.out.print(resolve(T,dp));

    }
    static int resolve(int n,int[] dp)
    {
        if( n == 1) return 0;
        if (dp[n] > 0)
        {
            return dp[n];
        }
        dp[n] = resolve(n-1,dp)+1;

        if(n%3 == 0)
        {
           Math.min(dp[n],resolve(n/3,dp)+1);
        }
        if(n%2 == 0)
        {
            Math.min(dp[n],resolve(n/2,dp)+1);
        }
        return dp[n];
    }
}