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))$이 시간복잡도가 된다.
구현
'Algorithm Theory > Dynamic Programming' 카테고리의 다른 글
| [DP] [BOJ 2579] 계단 오르기 (0) | 2020.03.30 |
|---|---|
| [DP] [BOJ 1003] 피보나치 함수 (0) | 2020.03.22 |
| [DP] [BOJ 1149] RGB거리 (0) | 2020.03.20 |
| [DP] [BOJ 11726] 2 x n 타일링 (0) | 2020.03.19 |
| [DP] [BOJ 9095] 1, 2, 3 더하기 (0) | 2020.03.18 |
댓글