[2163번] 초콜릿 자르기(C++, DP)

문제

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.

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

초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

 

문제접근법.

1. N X M 크기 초콜릿의 쪼개기 최솟값을 구하는 과정에서, i X j ( i < N, j < M) 쪼개기 최솟값이 이용될 것이다.

2. 다이나믹 프로그래밍으로 문제를 해결해야 한다.

3. 점화식을 생각해본다. 바로 점화식이 생각나지 않으면, 예시를 생각해본다( 2 X 3 )

 

예시.

2 X 3의 경우,

자르는 방법이 두 가지가 생길 수가 있다.

 

1. 세로로 자르는 경우

2 X 1, 2 X 2

 

2. 가로로 자르는 경우

1 X 3, 1 X 3

 

두 가지 경우를 관측해보면, 세로로 자를 경우에는 열(ROW)가 고정되어 있고, 가로로 자를 경우에는 행(COL)이 고정되어 있다. 2 X 3으로 직관적으로 이해가 되지 않는 경우에는, 더 큰 크기(4 X 5)를 관측해보면, 완벽하게 이해가 될 것이다.

 

해설코드(C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int N, M;
int dp[301][301] = { 0 };
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    memset(dp, 0, sizeof(dp));
 
    dp[1][1] = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int result = 301 * 301;
 
            // FIX ROW
            int c1 = 1;
            int c2 = j - 1;
            while (c1 <= c2) {
                result = min(result, dp[i][c1++] + dp[i][c2--]);
            }
 
            // FIX COL
            int r1 = 1;
            int r2 = i - 1;
            while (r1 <= r2) {
                result = min(result, dp[r1++][j] + dp[r2--][j]);
            }
 
            // RESULT
            if (result == 301 * 301)
                result = -1;
            dp[i][j] = result + 1;
        }
    }
 
    cout << dp[N][M] << endl;
    return 0;
}