(C++) 백준 2163 초콜릿 자르기

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

최소 쪼개기 개수를 찾으라는데
사실 어떻게 자르던 금을 따라 자르면 최소로 잘리게 된다

• 수식으로 표현하면 바로 (N-1) + N*(M-1) 이 답이다.
• DP로 풀면, DP[N][M] = NxM 크기를 1x1로 자르기 위한 (최소) 갯수를 만족하는 테이블을 만들어서 풀면 된다

#include <iostream>
#include <cstring>
using namespace std;

int dpTable[302][302];

int go(int n, int m){

    if(dpTable[n][m]!=-1) return dpTable[n][m];
    if(n==1) return dpTable[n][m] = m-1;
    if(m==1) return dpTable[n][m] = n-1;

    return dpTable[n][m] = go(1, m) + go(n-1, m) +1;
}

int main() {

    memset(dpTable, -1, sizeof(dpTable));

    int N,M;
    cin>>N>>M;

    cout<< go(N, M);


}