BOJ 2163번 : 초콜릿 자르기

dp 문제에서 찾기 힘든 낮은 랭크의 문제. 초콜릿 자르기다.

 

n*m인 초콜릿을 1*1 로 모두 자르는데 몇번을 쪼개야 하는지를 묻고 있다. 최소한으로 쪼개는 것이지만, 한번에 길게 자르는것을 생각하면 n*m 과 m*n 은 항상 같은 횟수를 가지게 된다.

 

dp문제를 풀때 첫번째로 해야하는것. 초기값 설정이다. 이 문제에서 초기값은 1*m 또는 m*1 크기의 초콜릿을 자르는 횟수가 될것 이고, 이는 m-1회 일것이다.

 

이후 해야 하는것. 점화식 세우기. 3*3을 생각해보면 아래 그림처럼 나눌수 있을 것이다.

이렇게 잘라보면, 3*1 조각과 3*2 를 각각 최소한으로 자르는 횟수 +1 이 될것이다.

 

dp[n][m]이 n*m을 최소한으로 자르는 횟수라고 가정하면,

dp[n][m] = 1+dp[n][1] +dp[n][m-1] 이고,

n*m 과 m*n은 항상 같으므로, 작은 수를 n 이라고 고정해주면 된다.

 

<소스코드>

#include<iostream>
#include<algorithm>
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
using namespace std;
int main() {
    int dp[302][302] = { 0, };
    int n, m = 0;
    cin >> n >> m;
    if (n == MAX(n, m)) {
        int temp = m;
        m = n;
        n = temp;
    }
    for (int i = 1; i < MAX(n,m)+1; i++)
        dp[1][i] = dp[i][1] = i - 1;
    for (int i = 2; i < n + 1; i++) {
        for (int j = i; j < m + 1; j++) {
            dp[i][j] = 1 + dp[i][1] + dp[i][j - 1];
        }
    }
    cout << dp[n][m];
}

 

문제 : 

https://www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기