본문 바로가기
Algorithm Theory/Dynamic Programming

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

by hyeyoo 2020. 3. 24.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

 

 

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

댓글