10803번 정사각형 만들기

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

boj dp 메모이제이션 캐시 cache 복습 코데 코딩 한국정보올림피아드

r을 무조건 작게, c는 크게 설정하였다.

또한, 21 ~ 23번 째 줄이 핵심인 것 같다. 3을 2로 하면, 틀린다. 

이유는 잘 모르겠다.. 

시간 초과 및 SOF 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 2e9
 
int R, C, cache[101][10001];
 
int simulation(int r, int c)
{
    if (r > c) return simulation(c, r);
    if (c % r == 0) return c / r;
 
    int &ret = cache[r][c];
    if (ret != -1) return ret;
 
    ret = INF;
 
    int q = c / r;
    int rmd = c % r;
 
    ret = min(ret, simulation(r, rmd) + q);;
 
    for (int i = 1; i <= r / 2; i++) {
        ret = min(ret, simulation(r - i, c) + simulation(i, c));
    }
 
    for (int i = 1; i <= c / 2; i++) {
        ret = min(ret, simulation(r, c - i) + simulation(r, i));
    }
    
    return ret;
}
 
int main()
{
    cin.tie(0);
    memset(cache, -1, sizeof(cache));
 
    scanf("%d %d", &C, &R);
    printf("%d\n", simulation(min(R, C), max(R, C)));
 
    return 0;
}

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 2e9
 
int R, C, cache[101][10001];
 
int simulation(int r, int c)
{
    if (r > c) return simulation(c, r);
    if (c % r == 0) return c / r;
 
    int &ret = cache[r][c];
    if (ret != -1) return ret;
 
    ret = INF;
 
    int q = c / r;
 
    if (q >= 3) {
        ret = min(ret, simulation(r, c - r) + 1);;
    }
    else
    {
        for (int i = 1; i <= r / 2; i++) {
            ret = min(ret, simulation(r - i, c) + simulation(i, c));
        }
 
        for (int i = 1; i <= c / 2; i++) {
            ret = min(ret, simulation(r, c - i) + simulation(r, i));
        }
    }
    
    return ret;
}
 
int main()
{
    cin.tie(0);
    memset(cache, -1, sizeof(cache));
 
    scanf("%d %d", &C, &R);
    printf("%d\n", simulation(min(R, C), max(R, C)));
 
    return 0;
}