[Baekjoon] 1463 - 1로 만들기

📝 문제

 

 

🔑 풀이 과정

· 다이나믹 프로그래밍 문제. 처음에는 이게 왜 DP인가 싶었긴 한데... 이건 그냥 내가 문제를 많이 안풀어봐서 그런듯.

표를 그려서 계산하다보면 점화식이 나온다. 그리고 이건 바텀-업 방식

 

· 풀이 과정

파란색 음영 들어간 부분이 최솟값을 의미

 

 

🔓 답안

import java.io.*;

public class Main {

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

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

        int[] D = new int[N+1]; //DP 배열 생성

        //DP 배열 채우기
        D[1] = 0;

        for(int i = 2; i <= N; i++){
            D[i] = D[i-1] + 1;
            if((i%2) == 0)
                D[i] = Math.min(D[i], D[i/2] + 1);
            if((i%3) == 0)
                D[i] = Math.min(D[i], D[i/3] + 1);
        }

        //출력
        bw.write(D[N] + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 다이나믹 프로그래밍