다이나믹프로그래밍- 초콜릿 자르기(백준 2163번)

1. 다이나믹프로그래밍(dynamic programming) 초콜릿 자르기(백준 2163번)

---

---

2. 다이나믹프로그래밍을 이용한 문제풀이

---

package dynamicProgramming;
 
import java.util.Scanner;
 
public class Main {
    static int[][] memo=new int[301][301];
    static void initMemo(int[][] memo) {
        for(int i=0;i<memo.length;i++) {
            for(int j=0;j<memo[i].length;j++) {
                memo[i][j]=0;
            }
        }
        for(int i=2;i<memo[1].length;i++) {
            memo[1][i]=i-1;
        }
    }
    static int cuttint(int n,int m) {
        if(n==1) {
            return memo[n][m];
        }
        return cuttint(n-1, m)+memo[1][m]+1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt();
        int m=sc.nextInt();
        initMemo(memo);
        System.out.println(cuttint(n, m));
    }
 
}
 

이 문제의 예를 들면 초콜릿이 (1,N) 모양이라면 이 초콜릿을 자를 수 있는 최소한의 수는 N-1 이라는 경우의 수가 나온다. 즉, 1,N(1<=N<=300) 의 초콜릿의 자를 수 있는 최소한의 수를 초기값으로 memo 배열에 넣어준다. (다이나믹 프로그래밍은 큰 문제를 잘게 쪼개가다가 맨 마지막 가장 작은 문제의 값을 이용하여 인접한 배열에 수를 채워가 마지막 결과값을 구하는 것이다.) 만약 초콜릿이 (3,4) 라면 cutting(3,4) 라는 함수에 들어간다.(이전에 memo배열을 초기화해주는 함수를 실행시켜준다.) 그러면 이 함수는 memo[3][3]=cutting(2,3)+memo[1][3]+1 가 된다. 이 뜻은 (3,3) 초콜렛을 (2,3)과 (1,3) 으로 쪼개주는 것이다. 여기에서 (2,3) 과 (1,3) 을 쪼개는 경우의 수 1을 더해주는 것이다. 그다음 (2,3) 은 앞의 N값이 2 이므로 한번더 쪼개기 위해 재귀호출을 한다. 하지만 (1,3) 은 이미 위의 memo배열에 초기화를 시켜줬으므로 재귀호출이 아니라 바로 값을 리턴해주는 것이다.(초기화 값을 이용해 재귀호출을 하는 것이 아니라 바로 결과값을 구할수 있다. 그러므로 불필요한 계산을 중복으로 하지 않는다.) 이런식으로 N값이 1이 될때까지 재귀호출을 반복하면 결과적으로 memo(3,3)에 결과값이 들어가게 되고 그 값을 리턴하게 된다.