코딩테스트공부

문제

[프로그래머스] 코딩테스트공부

접근

가장 어려웠던 문제

BFS DFS 가 여기서는 퍼포먼스가 안나와서 DP를 쓴다
경우의 수들을 비교해 나가고 그 경우의 수가 만들어내는 답 중에 최소값을 취함으로 최적의 방법을 찾아낸다

행렬의 위치에 값을 저장해나가고 저장한 값이 덮어씌워지려 하면 그 값을 비교하여 업데이트 한다

풀이

#include <vector>
#include <iostream>
using namespace std;

int maxAlp, maxCop;
int cache[151][151];

int solve(int alp, int cop, vector<vector<int>>& problems) 
{
    for (vector<int> v : problems) 
    {
        maxAlp = max(maxAlp, v[0]);
        maxCop = max(maxCop, v[1]);
    }
	if (alp >= maxAlp && cop >= maxCop) return 0;

    // 최댓값을 넘어갈 시 공간 크기 조정
    if (alp > maxAlp) alp = maxAlp;
    if (cop > maxCop) cop = maxCop;

    int& ret = cache[alp][cop];
    if (ret != 0) return ret;
    ret = 1e9;

    // 문제 풀이
    for (vector<int> v : problems) {
        int number = v[0];
        if (alp < v[0] || cop < v[1]) continue;
        ret = min(ret, solve(alp + v[2], cop + v[3], problems) + v[4]);
    }

    // 공부
    ret = min(ret, solve(alp + 1, cop, problems) + 1);
    ret = min(ret, solve(alp, cop + 1, problems) + 1);

    return ret;

}

int solution(int alp, int cop, vector<vector<int>> problems) {


    return solve(alp, cop, problems);
}

int main() {
    cout << solution(10, 10, {{10, 15, 2, 1, 2}, { 20, 20, 3, 3, 4 }});
}