[BOJ] 2163번: 초콜릿 자르기

2163번: 초콜릿 자르기

풀이

감이 안 잡혔는데 그냥 우리가 실제로 초콜릿을 쪼갤 때를 생각하면 된다. 보통 반으로 계속 쪼개지 않는가? 그걸 생각하며 관계식을 세우면 된다.
가로로 반으로 쪼갤 때 or 세로로 반으로 쪼갤 때 중 최솟값을 구하면 된다.

코드

#include <cstdio>
#include <algorithm>
int D[301][301], N, M;

int f(int n, int m)
{
    // 종료 조건
    if (n == 1)
        return D[n][m] = m - 1;
    else if (m == 1)
        return D[n][m] = n - 1;
    return D[n][m] = std::min(n * f(1, m) + (n - 1), m * f(n, 1) + (m - 1));
}

int main()
{
    scanf("%d %d", &N, &M);
    printf("%d\n", f(N, M));
    return 0;
}