• 코드: https://www.acmicpc.net/problem/1463

설명

DP에 대해 먼저 알아보자.

fib(n) 
{
	if(n = 1 or n = 2) 
    	then return 1;
        else return (fib(n-1) + fib(n-2));
}        

피보나치 수열을 재귀적으로 구하는 이 코드는 수가 점점 커지면 중복 호출이 f(1)과 f(2) 호출이 중복 발생한다.
만약 선형 시간 안에 구하고 싶다면 다음과 같다.

1) bottom-up

fib(n) 
{
	f[1] = f[2] = 1;
    for i = 3 to n
    	f[i] = f[i-1] + f[i-2];
    return f[n];
}    

아래에서 위로 저장해가면서 해를 구한다.

2) top-down

fib(n) 
{
	// 이전 호출 여부를 확인한다.
	if(f[n] != 0) then return f[n];
    else {
    	if (n == 1 or n ==2)
        	then f[n] <-1
        else 
        	f[n] <- fib(n-1) + fib(n-2);        
		return f[n];
}

이전 호출 여부를 확인하고, 재귀를 이용해서 계산한다.

두 방법 모두 메모 배열을 만들고 그곳에 결과를 저장해놓고 사용하는 방식이다. 작은 문제들을 연결하여 큰 문제를 해결하는 방식인 것이다.

내가 풀이한 방법은 다음과 같다. 만들어지는 숫자들을 Queue에 넣고 탐색하는 것이다. numbers 배열에 방문 횟수를 업데이트하고 만약 N == 1이 되면, key가 1일 때 value를 return 한다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class P1463 {
    static int N;
    static int[] numbers = new int[1000001];
    static int n_N;
    static int temp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        if (N == 1) {
            sb.append(0);
            System.out.println(sb);
            System.exit(0);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);

        while (true) {
            n_N = queue.poll();

            if (n_N % 3 == 0) {
                temp = n_N / 3;
                if (temp == 1) {
                    sb.append(numbers[n_N] + 1);
                    break;
                }
                if (numbers[temp] == 0) {
                    numbers[temp] = numbers[n_N] + 1;
                }
                queue.add(temp);
            }
            
            if (n_N % 2 == 0) {
                temp = n_N / 2;
                if (temp == 1) {
                    sb.append(numbers[n_N] + 1);
                    break;
                }
                if (numbers[temp] == 0) {
                    numbers[temp] = numbers[n_N] + 1;
                }
                queue.add(temp);
            }
            temp = n_N - 1;

            if (temp == 1) {
                sb.append(numbers[n_N] + 1);
                break;
            }
            if (numbers[temp] == 0) {
                numbers[temp] = numbers[n_N] + 1;
            }
            queue.add(temp);
        }

        System.out.println(sb);
    }
}

1. DP 사용 O
각 부분에 재귀호출을 하여 최솟값을 갱신한다.
예를들어, 6이 들어온다면 1) 3으로 나눠지는 경우, 2) 2로 나눠지는 경우, 3) 1을 빼는 경우가 있으므로 모두 재귀호출하여 3가지 경우 중 최솟값으로 DP를 갱신한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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.print(recur(N));
 
	}
 
	static int recur(int N) {
 
		if (dp[N] == null) {
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}
 
}

N이 6의 배수인 경우, 2와 3으로 모두 나누어 떨어짐을 기억해라! (이 조건은 찾기 한번 어려울 것 같다!!!)

2. DP 사용 X
재귀 호출할 때 연산 횟수를 같이 갱신시킨다. N=1이 되기 전까지 count를 누적하다 1이 되면 누적된 count를 반환하여 재귀를 탈출시킨다.

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
		System.out.println(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
	}
}

reference

• https://st-lab.tistory.com/133