[백준] 1로 만들기/자바

문제         

레벨: S4
알고리즘: DP
풀이시간: 
힌트 참조 유무:

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

1 번째 시도   

• 귀여운 수준의 구현이어서 바로 작성해보았다

import java.util.*;
import java.io.*;

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 cnt = 0;
        
        while(N != 1) {
            if(N%3 == 0) {
                N = N/3;
            }
            else if(N%2 == 0) {
                N = N/2;
            }
            else {
                N = N-1;
            }
         
            cnt++;
        }
        
        System.out.println(cnt);
    }
}

보란듯이 틀렸다.

• 이유는 3으로 먼저 나눌 수 있는지 검사하고 2로 나눌 수 있는지 검사하기 때문이다.
• 이 순서는 최솟값을 보장해주지 않는다.
• ex)
  • 내코드: 10 →  5 →  4 →  2 →  1로 4번 만에 만들 수 있다. 
  • 정답: 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

2 번째 시도  

• 2로 나누는 게 나은지 3으로 나누는 게 나은지 판단하려면 1까지 가봐야지 알 수 있다.
  • 둘 다 나눌 수 있을 때 2로 나누는 경우와 3으로 나누는 경우 dfs 함수를 만들어야 한다
  • 아무래도 시간제한이 있다보니 이 방법은 불가하다.
• 시간복잡도가 N인 DP를  사용하기로 한다
• dp배열에 전 숫자 +1로 초기화한다.
• 배열 이전 숫자들을 비교해서 값을 업데이트 해준다 
  • 2는 1번
  • 3은 1번
  • 4은 4/2 = 2의 정답인 1에서 +1한  2번
  • 5은 5-1 = 4의 정답인 2에서 +1한 3번

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

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[] dp = new int[N + 1];

        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]);
    }
}