[Java] 1463번 1로 만들기, 표로 이해

1. 문제 링크 및 문제

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

1-1 문제 요약

: 주어진 3가지 연산 방법으로 1을 얻을 수 있는 최소 연산횟수

2. 해결 방법 생각해보자 ...

최댓값이 10의 6승이므로 dp 를 사용해야겠구나!

3. 코드

import java.util.*;

public class Main {

    static int N;
    static int[] map;

    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N+1];

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

표로 이해
dp[10]까지 값이 어떻게 나오는 지 아래처럼 직접 계산해본다면 이해하기 도움된당

먼저, 2,3

dp[0], dp[1] = 0 ( 0은 사용X, 1은 초기값)

이므로, dp[2] = 1, dp[3] = 1

4,5

dp[4] = 2, dp[5] = 3

6, 7

dp[6] = 2, dp[7]= 3

8

dp[8] = 3

9,10

이렇게 해당 값을 얻을 수 있는 최소 연산횟수를 저장해둔 다음, 다음 숫자에도 계쏙 적용하는 방식이다.
처음에 dp 문제 너무 어려워 헤멨는데, 표로 정리하니 그나마 알 것 같다.
도움되는 이가 한 명이라도 있길 바라묘 . . .