[Java] 1463번. 1로 만들기 (#1차원 동적계획법)

문제링크 : https://www.acmicpc.net/problem/1463

상위문제를 해결하는 것은 하위문제의 여러개를 해결하는 것과 같고
하위문제들은 서로 중복되는 계산이 많은 경우에 '동적계획법' 사용가능

import java.io.*;

public class Main {
    public static int[] answer; // 계산값들을 기록할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n==1) { // 1인 경우의 출력
            System.out.println(0);
            return;
        }
        if (n == 2 || n == 3) { // 2,3인 경우의 리턴
            System.out.println(1);
        } else {
            answer = new int[n+1]; // 계산할 숫자+1 크기만큼 배열 생성
            answer[2] = 1;
            answer[3] = 1;
            for (int i = 4 ; i <= n ; i++){ // 4번째부터 목표 n까지의 값 계산
                switch (i%6){
                    case 1:
                    case 5: answer[i] = answer[i-1]+1; break;
                    case 2:
                    case 4: answer[i] = Math.min(answer[i/2],answer[i-1])+1; break;
                    case 3: answer[i] = Math.min(answer[i/3],answer[i-1])+1; break;
                    default: answer[i] = Math.min(answer[i/3],Math.min(answer[i/2],answer[i-1]))+1;
                }
            }
            System.out.println(answer[n]);
        }
    }
}