[백준 2163] 초콜릿 자르기

• N * M 크기의 초콜릿이 있는데 1 * 1 크기까지 초콜릿을 쪼갤 때 
• 쪼개기 횟수를 최소로 하는 방법
• Top-down 방식으로 DP 수행으로 해결 가능

---

dp(n, m) : n * m 인 크기의 초콜릿의 최소로 쪼갤 수 있는 횟수

0. 기저사례 : 문제에서 제시해준대로 1*1 의 크기가 되면 끝. 

 --> 더 이상 쪼갤 수 없기 때문에 return 0;

1. 한 변의 길이가 1인 경우 : 다른 변의 길이 - 1 이 쪼개는 최소 횟수

ex) 1 * 4 ---> 3회

 따라서, return (다른 변의 길이 - 1);

2. 변의 길이가 1이 아닌 경우 : 세로 방향/가로 방향으로 하나씩 자르면서 재귀함수 진행

#define MAX 300

using namespace std;

int dp[MAX + 1][MAX + 1];

int go(int n, int m) {

  // 0. 기저 사례

if (n == 1 && m == 1) {

return 0;

}

 // N*M 이나 M*N 자르는 횟수는 동일하다.

 // 따라서 dp[n][m] = dp[m][n] 

 // 참조자(&) 를 사용하여 배열의 정보 참조.

int& ret = dp[n][m];

int& ret2 = dp[m][n];

if (ret != -1) return ret;

if (ret2 != -1) return ret2;

  // 1. 한변의 길이가 1인 경우

if (n == 1 && m != 1) {

ret = m - 1;

ret2 = ret;

return ret;

}

else if (n != 1 && m == 1) {

ret = n - 1;

ret2 = ret;

return ret;

}

  //양변 모두 1이 아닌 경우

else {

int temp = 987654321;

//한 변의 반만 체크하면 계산이 됨

// 절반은 뒤집으면 같은 경우이기에

int num = n / 2;

for (int i = 1; i <= num; i++) {

temp = go(i, m) + go(n - i, m) + 1; //자른 두개의 초콜릿을 계산 + 자신의 경우의 수( 1 )

if (ret == -1) {

ret = temp;

ret2 = ret;

}

else {

ret = min(ret, temp);

ret2 = ret;

}

}

//세로, 가로 양쪽 실행

num = m / 2;

for (int i = 1; i <= num; i++) {

temp = go(n, i) + go(n, m - i) + 1;

if (ret == -1) {

ret = temp;

ret2 = ret;

}

else {

ret = min(ret, temp);

ret2 = ret;

}

}

return ret;

}

}

---

Review.

Top-down 방식으로 각 경우에 대해 나눠서 풀면 손쉽게 풀리는 문제.