[백준 1463] 1로만들기 - JAVA - [DP]

안녕하세요 놀이방사장입니다.

 

이번 포스팅은 백준 1463번

1로 만들기 문제입니다.

 

DP문제입니다.

1463번: 1로 만들기

 

이번 문제는 무작정 큰 수부터 나누면 안되는 문제입니다.

 

DP문제이기 때문에 값을 저장할 배열을 생성합니다.

그리고 나눌 수 있는 수는 3,2,1이 있는데 여기서 3,2,1 최소공배수 6도 같이 추가해서 풀어줘야합니다.

-> 재귀함수를 사용해서 가장 연산횟수가 가장값을 DP[N]배열에 저장해주면서 최솟값을 찾으면 됩니다.

-> 여기서 계산을 할 때 테이블에 값이 없을 떄 연산을 해줘야함

값이 있을 경우 RETURN으로 값을 불러와주면 됨

 

/*
 * 백준 1463 DP
 * 이모이제이션 사용
 * */

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

public class Main{
    static Integer[] dp;
    public static int getRecur(int n){
        if(dp[n] == null){
            if(n%6==0){
                dp[n] = Math.min(getRecur(n/3),Math.min(getRecur(n/2),getRecur(n-1))) +1;
            }else if(n%3==0){
                dp[n] = Math.min(getRecur(n/3),getRecur(n-1))+1;
            }else if(n%2==0){
                dp[n] = Math.min(getRecur(n/2),getRecur(n-1))+1;
            }else{
                dp[n] = getRecur(n-1)+1;
            }
        }
        return dp[n];
    };

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        dp = new Integer[n+1];
        dp[0] = dp[1] = 0;

        bw.write(String.valueOf(getRecur(n)));
        bw.flush();
        bw.close();
    }
}

 

감사합니다!