71 삐약 : 백준 1463| 1로만들기 [바킹독 문제 풀이|DP|JAVA]

https://www.acmicpc.net/problem/1463

 

 

package BKD_0x10_DP;

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

public class BOJ_1463 {
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N+1];
        dp[0] = dp[1]=0;

        System.out.println(recur(N));

    }
    static int recur(int N){
        if(dp[N] == null){
            if(N%6==0){
                dp[N] = Math.min(recur(N-1),Math.min(recur(N/3), recur((N/2))))+1;
                // 계산 되는 값들 중 가장 최소값을 다음 값으로 지정
                // 3과 2의 배수인 6의 경우일 때는 모든 경우의 수를 다 적용 해봐야 한다.

            }else if(N %3==0){
                dp[N] = Math.min(recur(N/3),recur(N-1))+1;

            } else if (N%2==0) {
                dp[N] = Math.min(recur(N/2),recur(N-1))+1;
            }else{
                dp[N] = recur(N-1)+1;
            }
        }
        return dp[N];
    }
}

 

 

DP를 처음 풀어보기 때문에 기존 풀이를 보며 흐름을 읽히는 데에 집중하며 풀었다.

또한 DP에대한 개념을 이해하며 풀이를 진행하였다.

 

참고 url :

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

https://st-lab.tistory.com/133

[백준] 1463번 : 1로 만들기 - JAVA [자바]