Backjoon(백준) 1463번 - 1로 만들기(Java)

어느정도 풀다가 막혀서 이 해설을 보시는 분은, 풀이 힌트를 한번 보고 다시 혼자서 풀어보세요

 

1. 풀이 힌트 

 - 따로 노트에 2부터 12까지 세로로 숫자를 나열 한뒤, 각 숫자가 1이 되는 최소값을 비교해보라 그러면 규칙이 보일 것이다. 그래도 안보인다면 케이스를 16까지 늘려보라.

 

2. 풀이 과정

 - 2부터 12까지 각 숫자를 1로 만드는 최소 연산횟수를 적어보면, 밑과 같이 나온다.

  2(1), 3(1), 4(2), 5(3), 6(2), 7(3), 8(3), 9(2), 10(3), 11(4), 12(2) // 괄호 안은 각 숫자를 1로 만드는 연산의 최소횟수

 1) 위의 결과를 기본으로 규칙을 찾기 위해 기본적으로 정수 N이 1씩 증가할 때 마다. 연산 횟수의 값도 1씩 증가한다고 가정한다. 

 ex) 3을 1로 만드는 최소 연산횟수는 1, 4를 1로 만드는 최소 연산횟수는 2

 2) 1)번과 같이 가정했을 경우 숫자 6의 최소 연산횟수는 5의 연산횟수 +1을 하여 4가 정답이어야 하지만 답은 3이다. 숫자7, 8, 9, 12도 전부 1번의 가정을 무시한다. 이럴 때는 새로운 규칙이 있다고 의심을 하고 그 규칙을 찾아야 한다.

 3) 새로운 규칙은 2가지가 있다. 주어진 숫자 N이 3으로 나눠지는 경우와 2로 나눠지는 경우이다.

   3-1) 2 또는 3으로 나눠지는 경우: 2또는 3으로 나눠지는 경우의 수들은 최소 연산횟수가 + 1씩 증가한다.

  ex) 3의 최소 연산횟수 = (1), 9의 최소 연산횟수 = (2)(3의 최소연산횟수  +1)

  ex) 2의 최소 연산횟수 = (1), 4의 최소 연산횟수 = (2), 8의 최소 연산 횟수 = (3)

  ex) 6의 최소 연산횟수 = (2), 12의 최소 연산횟수 = (3)

   3-2) 나머지 수 : 2또는 3으로 나눠지지 않는 숫자 N은 N-1의 최소 연산 횟수에서 +1을 한 값이다. (+1을 하는 이유는 -1을 수행하여 2 또는 3으로 나눠지는 수로 만들기 위해서임)

  ex) 5의 최소 연산횟수 = (3)(4의 최소 연산횟수 + 1), 7의 최소 연산횟수 = (3)(6의 최소 연산횟수 + 1)

4) 해당 규칙으로 식을 도출하여 코드로 구현한다.

 

3. 코드 구현

package dp2.backjoon;

import java.util.Scanner;

public class MakingOne {
    
    static int[] dp;

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        dp = new int[n + 1];
        
        System.out.println(dp3(n));
        System.out.println(dp2(n));
        sc.close();
    
    }
    static int dp2(int n) { // Top - down
        if (n == 1) {
            return 0;
        }
        if (dp[n] > 0) {
            return dp[n];
        }
        dp[n] = dp[n - 1] + 1;
        if (n % 2 == 0) {
            int temp = dp[n / 2] + 1;
            if (dp[n] > temp) {
                dp[n] = temp;
            }
        }
        
        if (n % 3 == 0) {
            int temp = dp[n / 3] + 1;
            if (dp[n] > temp) {
                dp[n] = temp;
            }
        }
        
        return dp[n];
    }
    
    static int dp3(int n) { // Bottom - up
        for (int i = 2; i <= n; i++) {
            
            dp[i] = dp[i - 1] + 1;
            if (i % 3 == 0) {
                int temp = dp[i / 3] + 1;
                if (dp[i] > temp) {
                    dp[i] = temp;
                }
            }
            if (i % 2 == 0) {
                int temp = dp[i / 2] + 1;
                if (dp[i] > temp) {
                    dp[i] = temp;
                }
                
            }        
       }
        return dp[n];
    }
} 

내 처음 풀이

 - 백준 채점에서는 계속 틀렸습니다가 나오는데 반례를 못 찾겠다.

 - 여튼 DP 정석 풀이대로 풀지 않았기 때문에 올바른 코드라고는 할 수 없다.

import java.util.Scanner;

public class MakingOne {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int count = 0;
        
        while (n != 1) {
            if (n % 3 == 0) {
                n = n / 3;
                count++;
                continue;
            }
            else if (n % 3 == 1) {
                n = (n - 1);
                count++;
                continue;
            }
            else if (n % 3 == 2 && n % 2 == 1) {
                n = (n - 1);
                count++;
                continue;
            }
            else if (n % 3 == 2 && n % 2 == 0) {
                n = n / 2;
                count++;
                continue;
            }
            else if (n % 2 == 0) {
                n = n / 2;
                count++;
                continue;
            }
            
        }
        System.out.println(count);
        sc.close();

    }

}

 

* 이번 문제 회고

역시 DP 문제는

규칙을 얼마나 깔끔하게 찾아서 점화식을 도출하는지가 제일 중요한 것 같다. 내 코드와 베스트 코드를 비교하면 알겠지만, 나도 어느정도 규칙을 찾았으나, 베스트 코드의 규칙은 깔끔하게 2가지 케이스로 나눠진데 반해 내가 찾은 규칙은 조건문이 5개나 쓰일 정도로 복잡하다. 결국 문제를 풀다가 내가 푼 것 처럼 복잡한 규칙이 나올 경우 더 간단한 풀이는 없는지 계속 의심하는게 중요하다.