[JAVA] 백준 (실버3) 1463번 1로 만들기

링크

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

---

문제 설명

(정답률 32.749%)
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
10의 경우에 10->9->3->1로 3번 만에 만들 수 있다.

---

입력 예제

10

---

출력 예제

3

---

정답 코드

1. x에 10이 입력된다고 할 때
   dp배열의 초기값은 { 0, 0, null, null, null, null, null, null, null, null, null } 이다.
   recur()메소드를 호출하면서 배열을 최솟값으로 계속 갱신한다.
2. recur()메소드에 10이 입력되면,
   10은 2의 배수이므로
   recur(10) -> min(recur(5), recur(9)) + 1
   다시 recur(5)와 recur(9)를 호출하게 되고
   recur(5) -> recur(4) + 1 = 3, recur(9) -> min(recur(3), recur(8)) + 1 = 2
   recur(4) -> min(recur(2), recur(3)) + 1 = 2
   recur(2) -> recur(1) + 1 = 1, recur(3) -> min(recur(1), recur(2)) + 1 = 1
   recur(10)은 recur(9)의 반환값인 dp[9]에 1을 카운트하여 3을 반환하게 된다.

import java.io.*;

public class Main {

    static Integer[] dp;	//메모이제이션 배열

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());

        dp = new Integer[x + 1];
        dp[0] = dp[1] = 0;	//래퍼 클래스의 배열의 기본 값은 null이므로 0과 1엔 0을 할당

        System.out.println(recur(x));
    }
	//재귀 메소드
    static int recur(int x) {
		
        if (dp[x] == null) {
        	//x가 6의 배수일 때
            if (x % 6 == 0) {
                dp[x] = Math.min(
                        recur(x - 1), Math.min(recur(x / 3), recur(x / 2))
                ) + 1;
            }
            //x가 3의 배수일 때
            else if (x % 3 == 0) {
                dp[x] = Math.min(recur(x / 3), recur(x - 1)) + 1;
            } 
            //x가 2의 배수일 때
            else if (x % 2 == 0) {
                dp[x] = Math.min(recur(x / 2), recur(x - 1)) + 1;
            } 
            //x가 2와 3의 배수가 아닐 때
            else {
                dp[x] = recur(x - 1) + 1;
            }
        }
        return dp[x];
    }



}

---

정리

동적 계획법(DP; Dynamic Programming) 문제이다.
메모이제이션(Memoization)은 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때,
이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여
전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법의 핵심이 되는 기술이다.