1로 만들기 - 1463번

---

풀이 방법 생각

DP 문제로 점화식을 생각해야 했다. 

일단 0과 1은 0번으로 고정이라서 값을 넣어주었다.

Bottom-up 방식으로 2부터 n까지 계산해 주었다.

 

1. 이전 수에서 1을 더하는 경우를 생각해서 이전 수의 횟수에서 1을 더해주는 경우
2. 2로 나누어 떨이지기 때문에 2로 나눈 수의 횟수에 1을 더하는 경우
3. 3으로 나누어 떨어지기 때문에 3으로 나눈 수의 횟수에 1을 더하는 경우

 

이 세가지를 비교해서 최솟값을 만들어 주었다.

 

내 코드

package com.company;

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;

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

        System.out.println(dp[n]);
    }

}