[BOJ] 백준 1463 1로 만들기

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

 Input 
10

 Output 

3

▶ 10 → 9 → 3 → 1 로 연산 3번 사용

 

[구현]

dp[i] = 숫자 i에 연산 횟수 최소 비용

        = 1 + Min(dp[i / 3] + dp[i / 2] + dp[i-1])

 

[x = 1]

→ result = 0

 

[x = 2]

    2 / 2 = 1

    2 - 1 = 1

→ result = 1

 

[x = 3]

    3 / 3 = 1

    3 - 1 = 2 / 2= 1

             = 2 - 1 = 1

→ result = 1

 

[x = 4]

    4 - 1 = 3/ 3 = 2

    4 / 2 = 2 / 2 = 1

             = 2 - 1 = 1

→ result = 2

 

[x = 9]

    ※9는 2로 나누어 떨어지지 않습니다.

    dp[9] = 1 + Min(dp[9/3], dp[9-1]) = 1 + Min(dp[3], dp[8])

              = 1 + Min(1 + Min(dp[2], dp[1]), 1 + Min(dp[4], dp[7]))

              = 1 + Min(1+0, 1 + Min(1 + Min(dp[3], dp[2]), 1 + Min(dp[6]))

              = 1 + 1 

→ result = 2

 

[x = 10]

   ※10은 3으로 나누어 떨어지지 않습니다. 

    dp[10] = 1 + Min(dp[10/2] + dp[10-1])

→ result = 3

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        // 문제 조건 상 n >= 1
        int n = Integer.parseInt(sc.nextLine());
         
        // 인덱스를 1부터 조작하기 위함
        int[] dp = new int[n+1];
         
        dp[1] = 0;
        for(int i=2; i<=n; i++) {
            if( (i % 2 == 0) && (i % 3 == 0)) {
                dp[i] = 1 + Min(dp[i/3], dp[i/2], dp[i-1]);
            }else if( i % 3 == 0) {
                dp[i] = 1 + Min(dp[i/3], dp[i-1]);
            }else if( i % 2 == 0) {
                dp[i] = 1 + Min(dp[i/2], dp[i-1]);
            }else {
                dp[i] = 1 + dp[i-1];
            }
        }
         
        // 결과 출력
        System.out.println(dp[n]);
         
    }
 
    private static int Min(int ...arr) {
        int min = arr[0];
        for(int i = 1; i < arr.length; i++) {
            min = min < arr[i] ? min : arr[i];
        }
        return min;
    }
}