백준 2163 초콜릿 자르기

// 12분
#include <cstdio>
using namespace std;
 
int d[301][301];
 
int dp(int n, int m) {
    if (d[n][m] > 0) return d[n][m];
    if (n == 1 && m == 1) return 0;
    if (n == 1)
        return d[n][m] = dp(n, m / 2) + dp(n, m - m / 2) + 1;
    else
        return d[n][m] = dp(n / 2, m) + dp(n - n / 2, m) + 1;
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%d\n", dp(n, m));
    return 0;
}
 

다이나믹 프로그래밍 문제

이 문제는 정말 쉽다. 단순하게 n*m-1을 출력해도 정답 처리가 된다.

하지만 dp문제를 풀기로 했으므로 dp다운 접근을 하여 코드를 짰다.