백준 1463번 (db 점화식) 다시 !!

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

import java.util.*;

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

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

    int[] db = new int[N+1];

    db[1] = 0;

int count = 0;

// N = 5 db[2] = db[1] + 1 db[3]

for (int i = 2 ; i <= N; i++)
{

db[i] = db[i - 1] + 1;


            if (i % 3 == 0 ) {

               db[i] = Math.min(db[i],db[i/3]+1);

            }

            if (i % 2 == 0 ) {

               db[i]= Math.min(db[i],db[i/2] + 1);

            }

}

    System.out.println(db[N]);







}

}
db를 이용하여 문제를 푸는 문제이다. 점화식을 이용하여 3으로 나누어질때는 1을 빼는 것과 3으로 나누고 +1을 한 것중에 작은 값을 선택하는 식으로 구하는 것이었다. 2로 나누어질때도 마찬가지다. 점화식을 만든다는 것 자체가 상당히 중요하고 이러한 생각을 하는게 좋은 발상인 것 같다. 이러한 발상은 다시 한번 봐도 좋은 것 같다.