19. 코딩 테스트 공부

https://school.programmers.co.kr/learn/courses/30/lessons/118668

원래는 dp[max_a][max_b]로 구하려고 했으나 max_a, max_b보다 큰 값에서 최대가 나올 수도 있었다.
그래서 dp[alp][cop]로 계산을 했는데 중간에 a > max_a, b > max_b가 된다면 이를 a = max_a, b = max_b로 처리해야 시간 초과, 메모리 초과가 나지 않는다. 이 부분에 유의해야 한다.

또한 dp 테이블을 dp[max_a][max_b] 를 구하기 위해서 dp[max_a - A][max_b - B] 를 구하는 형태로 접근할 수도 있으나 문제는 알고력과 코딩력을 향상시키는 끝 지점이 max_a, max_b가 아닐 수도 있다는 점 이었다. (그 이상의 값에서 끝날 수도 있음)
따라서 해당 dp 테이블이 정답이 아닐 수 있으므로 이 문제는 dp[max_a + A][max_b + B] 로 접근하는 것이 맞다고 볼 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> vi;
const int N = 152;
int dp[N][N];
int mx_a, mx_b;

int solve(int a, int b, vi &p)
{
    if (a == mx_a && b == mx_b) return 0;
    int &ret = dp[a][b];
    if (ret != -1) return ret;
    ret = 1e9;
    if (a < mx_a) ret = min(ret, solve(a + 1, b, p) + 1);
    if (b < mx_b) ret = min(ret, solve(a, b + 1, p) + 1);
    
    for (auto to : p)
    {
        int ra = to[0], rb = to[1], ga = to[2], gb = to[3], t = to[4];
        if (a >= ra && b >= rb)
            ret = min(ret, solve(min(mx_a, a + ga), min(mx_b, b + gb), p) + t);
    }
    
    return ret;
}

int solution(int alp, int cop, vi p)
{
    memset(dp, -1, sizeof dp);

    for (auto to : p)
    {
        int a = to[0], b = to[1];
        mx_a = max(mx_a, a), mx_b = max(mx_b, b);
    }
    
    return solve(alp, cop, p);
    
    // cout << mx_a << ' ' << mx_b << endl;
    // 약간 넘어갈 수도 있고 그 값이 최적일수도 있음
    // int ans = 1e9;
    
    // for (int i = mx_a; i < 500; i++) for (int j = mx_b; j < 500; j++)
        // ans = min(ans, solve(i, j, p));
    
    // return ans;
}