[DP] [BOJ 2163] 초콜릿 자르기

 

2163번: 초콜릿 자르기

문제

N x M 초콜릿을 1 x 1 초콜릿으로 자르는 최소 횟수를 구하는 문제

 

해석

이 문제는 DP로도 풀 수 있고 수학으로도 풀 수 있는데, 여기서는 DP로 접근해보자. 우선, 초콜릿은 자르면 더 작은 초콜릿으로 나누어지기 때문에, 큰 문제를 작은 문제로 나눌 수 있다. 따라서 그림을 보면서 이해해보자.

 

임의의 초콜릿은 가로, 세로로 자를 수 있다.

N x M 초콜릿이 있다고 할 때, 초콜릿을 세로로 자르거나 가로로 자를 수 있다. 이를 식으로 표현해보자.

세로로 자른다 : N x M = (N) x (M - K) 초콜릿 + (N) x (K) 초콜릿

가로로 자른다 : N x M = (N - K) x (M) 초콜릿 + (K) x (M) 초콜릿

 

초콜릿을 자르는 경우, 더 작은 초콜릿으로 나눌 수 있고, 각각의 작은 초콜릿을 자르는 최소 횟수부터 우리가 원하는 N x M 초콜릿을 자르는 최소 횟수를 구할 수 있으므로, 이 문제는 DP로 풀 수 있다. 식도 위의 것을 사용해서 풀 수 있다. 자세한 설명은 코드로 대체하겠다.

 

시간복잡도

초콜릿은 최대 M x N개가 있으며, 각각의 초콜릿을 자르는 경우는 (M - 1) + (N - 1)이므로 $O(MN(M + N))$이 시간복잡도가 된다.

 

구현

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class Main {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	br.close();
	int d[][] = new int[N + 1][M + 1];
	for(int n = 1; n <= N; n++) {
	for(int m = 1; m <= M; m++) {
	d[n][m] = Integer.MAX_VALUE;
	}
	}
	d[1][1] = 0;
	for(int n = 1; n <= N; n++) {
	for(int m = 1; m <= M; m++) {
	if (n == 1 && m == 1)
	continue;
	for(int k = 1; k < n; k++) {
	d[n][m] = Math.min(d[n][m], d[n - k][m] + d[k][m] + 1);
	}
	for(int k = 1; k < m; k++) {
	d[n][m] = Math.min(d[n][m], d[n][m - k] + d[n][k] + 1);
	}
	}
	}
	System.out.println(d[N][M]);
	}
	}

view raw BOJ_2163.java hosted with ❤ by GitHub