Bonjour, tout le monde!

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

Algorithm Theory/Dynamic Programming

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

hygoni 2020. 3. 24. 00:29

 

 

2163번: 초콜릿 자르기

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와

www.acmicpc.net

문제

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))$이 시간복잡도가 된다.

 

구현

 

 

0 Comments
댓글쓰기 폼