10805번 L 모양의 종이 자르기

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

dp cache 캐시 동적계획법 복습 냅색 메모이제이션 필수 코테 코딩 추천

비슷한 문제 : https://hsdevelopment.tistory.com/526

별로 이해는 안 되겠지만 그림 첨부.

왼쪽은 행으로 짜르는 것이다. i가 점점 증가하는 방향을 잘 보면서, h1, h2, w1, w2가 어떻게 변화되는지 살펴보자.

오른쪽은 열을 기준으로 짜르는 것이고, i의 방향을 잘 보자.

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 2e9
 
int cache[55][55][55][55], rec[55][55];
 
int rect(int r, int c)
{
    /*if (r <= 0 || c <= 0) {
        return INF;
    }*/
 
    if (r > c) return rect(c, r);
    if (c % r == 0) return c / r;
 
    int &ret = rec[r][c];
    if (ret != -1) return ret;
    
    ret = INF;
 
    int q = c / r;
    
    if (q >= 3) {
        ret = min(ret, rect(r, c - r) + 1);
    }
    else {
 
        // r이 짝수일 경우 깨끗하게 나누어지므로, 여기에서는 부등호가 '<='를 사용한다.
        for (int i = 1; i <= r / 2; i++) {
            ret = min(ret, rect(r - i, c) + rect(i, c));
        }
 
        for (int i = 1; i <= c / 2; i++) {
            ret = min(ret, rect(r, c - i) + rect(r, i));
        }
    }
 
    return ret;
}
 
int simulation(int h1, int w1, int h2, int w2)
{
    /*if (h1 <= 0 || w1 <= 0 || h2 <= 0 || w2 <= 0) {
        return INF;
    }*/
 
    int &ret = cache[h1][w1][h2][w2];
 
    if (ret != -1) return ret;
 
    ret = INF;
 
    // 부등호 조심! '<='을 사용하면, rect() 함수 내 if (c % r == 0) return c / r; 오류 발생
    for (int i = 1; i < h1; i++) {
        if (i < h2) {
            ret = min(ret, simulation(h1 - i, w1, h2 - i, w2) + rect(min(i, w1 - w2), max(i, w1 - w2)));
        }
        else if (i == h2) {
            ret = min(ret, rect(min(i, w1 - w2), max(i, w1 - w2)) + rect(min(h1 - i, w1), max(h1 - i, w1)));
        }
        else {
            ret = min(ret, simulation(i, w1, h2, w2) + rect(min(h1 - i, w1), max(h1 - i, w1)));
        }
    }
 
    // 부등호 조심! '<='을 사용하면, rect() 함수 내 if (c % r == 0) return c / r; 오류 발생
    for (int i = 1; i < w1; i++) {
        if (i < w2) {
            ret = min(ret, simulation(h1, w1 - i, h2, w2 - i) + rect(min(i, h1 - h2), max(i, h1 - h2)));
        }
        else if (i == w2) {
            ret = min(ret, rect(min(h1, w1 - i), max(h1, w1 - i)) + rect(min(i, h1 - h2), max(i, h1 - h2)));
        }
        else {
            ret = min(ret, simulation(h1, i, h2, w2) + rect(min(h1, w1 - i), max(h1, w1 - i)));
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    memset(cache, -1, sizeof(cache));
    memset(rec, -1, sizeof(rec));
 
    int h1, w1, h2, w2;
 
    scanf("%d %d %d %d", &h1, &w1, &h2, &w2);
    printf("%d\n", simulation(h1, w1, h2, w2));
 
    return 0;
}