[JAVA/알고리즘] 동적 계획법 Dynamic Programming (백준 1463)

동적 계획법 Dynamic Programming (DP) 란, 

하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장 후 큰 문제를 해결하는 방법

 

작은 문제의 답을 저장 (메모이제이션) 후 재활용

 

 

조건

1. 겹치는 문제 (Overlapping Subproblems) : 동일한 작운 문제들이 반복되는 경우

2. 최적 부분 구조 (Optimal Substructure) : 부분 문제 최적값을 사용하여 전체 문제 최적값 구할 수 있는 경우

 

구현 방식 

1. Top-Down (Memoization) : 재귀함수를 사용하여 구현

2. Buttom-Up (Tabulation) : 반복문을 사용하여 구현 

 

---

 [백준 1463] 1로 만들기

1. Top-Down 방식 (재귀함수) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static Integer[] d;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // Integer 배열은 기본값이 null
        d = new Integer[n+1];
        d[0] = d[1] = 0;

        f(n);

        System.out.println(d[n]);
    }

    private static int f(int x) {
        if (d[x] == null) {
            d[x] = f(x-1) + 1;
            if (x % 2 == 0) {
                int tmp = f(x / 2) + 1;
                d[x] = d[x] < tmp ? d[x] : tmp;
            }
            if (x % 3 == 0) {
                int tmp = f(x / 3) + 1;
                d[x] = d[x] < tmp ? d[x] : tmp;
            }
        }
        return d[x];
    }
}

*) Math.min을 이용하여 재귀함수를 구현할 경우 시간 초과가 발생하여 if 문을 이용하여 구현

 

 

2. Buttom-Up 방식 (반복문) 

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int d[] = new int[n+1];
        d[1] = 0;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if(i % 2==0) {
                d[i] = Math.min(d[i], d[i/2] + 1);
            }
            if (i % 3 ==0) {
                d[i] = Math.min(d[i], d[i/3] + 1);
            }
        }
        System.out.println(d[n]);
    }
}

 

 

어떤 정수 n에 대하여, n이

 

2의 배수일 경우,

3의 배수일 경우,

2와 3의 배수일 경우, 

그렇지 않은 경우

 

로 나뉠 수 있다. 

 

모든 정수는 result(n-1) + 1의 값을 결과값으로 가질 수 있고 2 또는 3의 배수일 경우 다른 값을 결과값으로 가질 수 있다.

 

예를 들면, n이 12이라고 할 때

12의 결과값으로 result(11) + 1의 값을 갖거나, 

result(6)  + 1의 값을 갖거나                                -> 12 = 6 * 2 이므로 6의 결과값에 1을 더함 

result(4) + 1의 값을 가질 수 있다.                       -> 12 = 4 * 3 이므로 4의 결과값에 1을 더함

 

이 중 최솟값을 구하는 문제이므로 점화식을 세우자면, 최솟값 배열을 d[] 라고 하고 임의의 정수 i라고 하여

// 1을 빼는 경우
d[i] = d[i-1] + 1;

// 2로 나누는 경우
if(i % 2==0) {
	d[i] = Math.min(d[i], d[i/2] + 1);
}

// 3으로 나누는 경우
if (i % 3 ==0) {
	d[i] = Math.min(d[i], d[i/3] + 1);
}

 

 

 

 

<참고 자료>

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

https://stdio-han.tistory.com/109

백준 1463번: 1로 만들기[JAVA]

https://tears-of-debugging.tistory.com/32

[백준-1463번 자바/java] 1로 만들기 _디버깅의 눈물