[그래프(다익스트라), DP] 프로그래머스 코딩 테스트 공부 C++

 

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

프로그래머스

다익스트라

#include <string>
#include <vector>
#include <queue>
#define INF 10001

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int dist[151][151];
    fill(&dist[0][0], &dist[150][151], INF);
    problems.push_back({0,0,1,0,1}); // 공부 추가
    problems.push_back({0,0,0,1,1});
    
    int goal_alp = 0, goal_cop = 0;
    for(auto p : problems) {
        goal_alp = max(goal_alp, p[0]);
        goal_cop = max(goal_cop, p[1]);
    }

    priority_queue<vector<int>, vector<vector<int>>, greater<>> pq; // 오름차순
    pq.push({0, alp, cop});
    dist[alp][cop] = 0;
    while(!pq.empty()) {
        auto now = pq.top();
        pq.pop();
        
        if (dist[now[1]][now[2]] < now[0]) continue;
        
        for(auto p : problems) {
            if ((now[1] < p[0]) || (now[2] < p[1])) continue; // 못 푸는 문제

            int next_alp = min(now[1]+p[2], goal_alp);
            int next_cop = min(now[2]+p[3], goal_cop);
            if (dist[next_alp][next_cop] <= dist[now[1]][now[2]] + p[4]) continue; // = 없으면 효율성 통과X
            dist[next_alp][next_cop] = dist[now[1]][now[2]] + p[4];
            pq.push({dist[next_alp][next_cop], next_alp, next_cop});
        }
    }
    
    return dist[goal_alp][goal_cop];
}

DP

Bottom-Up

#include <string>
#include <vector>
#define INF 10001

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int dp[151][151]; // dp[alp][cop] := 최소 공부 시간
    fill(&dp[0][0], &dp[150][151], INF);
    
    int goal_alp = 0, goal_cop = 0;
    for(auto p : problems) {
        goal_alp = max(goal_alp, p[0]);
        goal_cop = max(goal_cop, p[1]);
    }
    alp = min(alp, goal_alp); // 4, 7, 8, 10 TC
    cop = min(cop, goal_cop);

    dp[alp][cop] = 0;
    for(int i=alp; i<=goal_alp; i++) {
        for(int j=cop; j<=goal_cop; j++) {
            if (i < goal_alp) dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1);
            if (j < goal_cop) dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1);
            for(auto p : problems) {
                if ((p[0] <= i) && (p[1] <= j)) {
                    int next_alp = min(i+p[2], goal_alp);
                    int next_cop = min(j+p[3], goal_cop);
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][j]+p[4]);
                }
            }
        }
    }
    
    return dp[goal_alp][goal_cop];
}

Top-Down

시간 초과

#include <string>
#include <vector>
#include <cstring>
#define INF 10001

using namespace std;

int goal_alp = 0;
int goal_cop = 0;
int dp[151][151];

int func(int alp, int cop, vector<vector<int>>& problems) {
    if (goal_alp <= alp && goal_cop <= cop) return 0;

    int& result = dp[alp][cop];
    if (result != -1) return result;

    result = INF;
    result = min(result, func(min(goal_alp, alp + 1), cop, problems) + 1);
    result = min(result, func(alp, min(goal_cop, cop + 1), problems) + 1);

    for (auto p : problems) {
        if (alp < p[0] || cop < p[1]) continue;
        result = min(result, func(min(goal_alp, alp+p[2]), min(goal_cop, cop+p[3]), problems) + p[4]);
    }

    return result;
}

int solution(int alp, int cop, vector<vector<int>> problems) {
    memset(dp, -1, sizeof(dp));

    for (auto p : problems) {
        goal_alp = max(goal_alp, p[0]);
        goal_cop = max(goal_cop, p[1]);
    }

    return func(alp, cop, problems);
}