2022 KAKAO TECH INTERNSHIP / 코딩 테스트 공부

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

프로그래머스

#include <string>
#include <vector>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

vvi dp;
int N;

int solution(int alp, int cop, vector<vector<int>> problems) {
    N = 151;
    dp.resize(N, vi(N, 987654321));
    dp[alp][cop] = 0;

    int dest_alp = 0, dest_cop = 0;
    for (auto p : problems) {
        dest_alp = max(dest_alp, p[0]);
        dest_cop = max(dest_cop, p[1]);
    }

    alp = min(alp, dest_alp);
    cop = min(cop, dest_cop);

    for (int i = alp; i <= dest_alp; ++i) {
        for (int j = cop; j <= dest_cop; ++j) {
            dp[i][j] = i - alp + j - cop;
        }
    }

    for (auto p : problems) {
        for (int i = max(alp, p[0]); i <= dest_alp; ++i) {
            int ii = min(i + p[2], dest_alp);

            for (int j = max(cop, p[1]); j <= dest_cop; ++j) {
                int jj = min(j + p[3], dest_cop);
                dp[ii][jj] = min(dp[ii][jj], dp[i][j] + p[4]);
            }
        }
    }

    for (auto p : problems) {
        for (int i = max(alp, p[0]); i <= dest_alp; ++i) {
            int ii = min(i + p[2], dest_alp);

            for (int j = max(cop, p[1]); j <= dest_cop; ++j) {
                int jj = min(j + p[3], dest_cop);
                dp[ii][jj] = min(dp[ii][jj], dp[i][j] + p[4]);
            }
        }
    }

    /*for (int i = alp; i <= dest_alp; ++i) {
        for (int j = cop; j <= dest_cop; ++j) {

            for (auto p : problems) {
                if (i < p[0] || j < p[1]) continue;
                int ii = min(i + p[2], dest_alp);
                int jj = min(j + p[3], dest_cop);
                dp[ii][jj] = min(dp[ii][jj], dp[i][j] + p[4]);
            }
        }
    }*/

    return dp[dest_alp][dest_cop];
}

dp 업데이트 순서를 고려