[백준] 1463번 : 1로 만들기 자바(JAVA) 풀이

문제

---

---

문제 탐색하기

• 1을 만들 수 있는 최소 연산 횟수 구하기 
• 가능한 연산
  • 3으로 나누어 떨어지는 경우, 3으로 나누기
  • 2으로 나누어 떨어지는 경우, 2으로 나누기
  • 1로 빼기
• 경우의 수 구하기
  • 2와 3 둘 다 나누어 떨어지는 경우
  • 3으로 나누어 떨어지는 경우
  • 2로 나누어 떨어지는 경우
  • 2와 3 둘 다 나누어 떨어지지 않는 경우

가능한 시간복잡도

입력 범위 ( 1 ≤ N ≤ 10^6)

동적계획법을 사용하여 최악의 경우 시간 복잡도는 O( N ) 

 

잘못된 코드

처음에는 이런 식으로 코드를 구현했었는데,

10을 1로 만드는 과정에서 오류가 생긴다.

e.g. 10 → 9 → 3 → 1 (연산 횟수 : 3) 이 되어야하는데 10 → 5 → 4 → 2 → 1 (연산 횟수 : 4) 가 되어버린다.

최소 연산 횟수를 구하는데 사용하는 연산이 정해져있는게 아니라 모든 연산을 통한 후 최소 연산 횟수를 구할 수 있다. 

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 result = cal(n);
        System.out.println(result);
    }

    public static int cal(int n) {
        int count = 0;
        while(n > 1){
            if(n % 6 == 0){ // 2와 3 둘 다 나눠 떨어지는 경우
                n = n/3;  
            } else if(n % 3 == 0){ // 3으로 나눠 떨어지는 경우
                n = n/3;
            } else if(n % 2 == 0){ // 2로 나눠 떨어지는 경우
                n = n/2;
            } else { // 2와 3 둘 다 나눠 떨어지지 않는 경우
                n = n - 1;
            }
            count++;
        }
        return count;
    }
}

 

---

코드 설계하기

• 최소 연산 횟수를 구할 정수 N을 입력받아 변수에 저장한다.
• 모든 값에 대한 최소 연산 횟수를 저장할 배열 dp 를 선언한다. (Integer 형)
• 경우의 수를 구한다
  • 2와 3 둘 다 나누어 떨어지는 경우
    • 1 빼기
    • 2로 나누기
    • 3으로 나누기
  • 3으로 나누어 떨어지는 경우
    • 3으로 나누기
    • 1 빼기
  • 2로 나누어 떨어지는 경우
    • 2로 나누기
    • 1빼기
  • 2와 3 둘 다 나누어 떨어지지 않는 경우
    • 1빼기
•  

   4. 결과를 출력한다.

---

풀이 코드

※ Math.min으로 최소 연산 횟수를 구할 때 ,   n-1인 경우부터 검사하면 시간 초과가 난다. n/3이나 n/2 먼저 호출하면 1까지 빠르게 도달하기 때문에 먼저 호출하도록 하자 !

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

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

        dp = new Integer[n+1];
        dp[0] = dp[1] = 0;
        
        System.out.println(cal(n));
    }

    public static int cal(int n) {
        if(dp[n] == null) { // 최소 연산 횟수가 구해지지 않은 경우
            if(n % 6 == 0){ // 2와 3 둘 다 나눠 떨어지는 경우
                // 3가지 경우의 수 중 최소 연산 횟수를 가져옴 + 연산 횟수 1
                dp[n] = Math.min(cal(n-1), Math.min(cal(n/2), cal(n/3))) +1;
            } else if(n % 3 == 0){ // 3으로 나눠 떨어지는 경우
                dp[n] = Math.min(cal(n/3), cal(n-1)) + 1;
            } else if(n % 2 == 0){ // 2로 나눠 떨어지는 경우
                dp[n] = Math.min(cal(n/2), cal(n-1)) + 1;
            } else { // 2와 3 둘 다 나눠 떨어지지 않는 경우
                dp[n] = cal(n-1) + 1;
            }
        }
        return dp[n];
    }
}