카카오기출 코딩테스트 공부 c++

결국... 못풀고 참고했다..

 

배울점은 매개변수 인자가 &일때를 생각해야 된다는 것이다!! 2차원 배열같은 큰 컬렉션은 &로 받으면서 참조를 통해 시간을 단축시킬 수 있다!

 

다시 보기.. ㅜㅜ 

 

DP + 메모이제이션으로 푸는 문제였다.

 

 

#include <bits/stdc++.h>
        using namespace std;

        int maxAlp, maxCop;
        int cache[151][151]; //현재 alp,cop만큼의 능력이 있을때, 

        int solve(int alp, int cop, vector<vector<int>>& problems) {
        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) {
        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) {
        for(vector<int> v: problems) {
        maxAlp = max(maxAlp, v[0]);
        maxCop = max(maxCop, v[1]);
        }

        return solve(alp, cop, problems);
        }