[PS] 백준 1463번 1로 만들기 - DP

문제

예제

코드

import java.util.Scanner;

public class Main {

    static Integer[] dp;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        dp = new Integer[N+1];
        dp[0] = dp[1] = 0;

        System.out.println(caculate(N));

    }

    static int caculate(int n) {

        if(dp[n] == null) {
            if(n%6==0) {
                dp[n] = Math.min(Math.min(caculate(n/2),caculate(n/3)),caculate(n-1)) + 1;
            }
            else if(n%3 == 0) {
                dp[n] = Math.min(caculate(n/3), caculate(n-1)) +1;
            }
            else if(n%2 == 0) {
                dp[n] = Math.min(caculate(n/2), caculate(n-1)) +1;
            }
            else {
                dp[n] = caculate(n-1) +1;
            }
        }
        return dp[n];
    }
}

코드 풀이

처음에는 연산을 할때마다 카운트를 해서 리턴하려고 했지만 생각보다 복잡해서
금방 접고 찾아봤더니 DP 계산법으로 푸는 방법이 있었다.

DP가 뭔지 모르겠어서 이 게시글을 참고했다.
그리고 나서 이 풀이를 참고했다.

참고한 풀이를 해석해보면 이렇다.
우선 재귀함수를 f(i), 그 결과를 dp[i]라고 칭한다.
결과 배열은 비어있지만
f(0)과 f(1)의 결과 dp[0],dp[1]은 0으로 미리 저장해둔다.

예시로 4의 경우를 보자.
f(4)가 호출되면, 처음에는 결과 배열이 비어있으므로 dp[4]는 null이다.
4는 2의배수이므로
dp[4] = f(4/2=2)와 f(4-1=3) 이 코드를 호출한다.

1. f(2) -> 2의 배수
   min(f(2/2=1),f(2-1=1))
   dp[1]=0. dp[1]=0이므로 0+1 ->dp[2]=1 저장 (최소연산횟수 1번)
   (+1하는 것은 이번에 재귀함수를 호출한 연산횟수를 더하기 위함이다)
2. f(3) -> 3의 배수
   min(f(3/3=1),f(3-1=2))
   dp[1]=0, dp[2]=1이므로 0+1 -> dp[3]=1을 저장(최소연산횟수 1번)

f(4)로 다시 돌아와서
min(f(2),f(3)) 에서
dp[2]=1, dp[3]=1 이므로 1+1 -> dp[4]=4를 저장하고 해당 값을 return한다.

이런 식으로 dp배열에 연산횟수가 누적되어 저장되고, 원하는 값을 얻을 수 있다. 이런 방식을 메모이제이션이라고 한다.