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

프로그래머스 코딩 테스트 공부 [2022 KAKAO TECH INTERNSHIP]
https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

문제 풀이

• 이 문제는 DP, 다익스트라 알고리즘으로 풀 수 있습니다. 
• DP의 경우 dp[알고력][코딩력] 배열이 해당 알고, 코딩력이 되는 최소 시간을 가지도록 하고 공부와 문제 풀이를 통해 알고력, 코딩력을 높이는 것을 고려하며 최소 시간을 업데이트 하며 dp[목표 알고력][목표 코딩력]의 값을 계산합니다.
• 다익스트라 알고리즘의 경우 시간을 기준으로 다익스트라 알고리즘을 적용하여 목표 알고력과 목표 코딩력에 도달했을 때 해당 시간을 리턴하도록 합니다.

코드 (DP)

#include <vector>

using namespace std;

#define MAX 200

int dp[MAX][MAX];

int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = 0, max_cop = 0;
    for(auto p: problems) {
        max_alp = max(max_alp, p[0]);
        max_cop = max(max_cop, p[1]);
    }
    
    // 초기 알고력, 코딩력이 목표치를 넘어있을 경우 아래 반복문들이 실행되지 않는
    // 경우를 방지하기 위해 둘 중의 최솟값을 취함
    alp = min(alp, max_alp);
    cop = min(cop, max_cop);
    
    for(int i=alp; i<=max_alp; ++i) {
        for(int j=cop; j<=max_cop; ++j) {
            dp[i][j] = 1e6;
        }
    }
    
    dp[alp][cop] = 0;
    for(int i=alp; i<=max_alp; ++i) {
        for(int j=cop; j<=max_cop; ++j) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1); // 알고리즘 공부
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1); // 코딩 공부
            
            for(auto p: problems) {
                if(i >= p[0] && j >= p[1]) { // 문제 풀 수 있다면 풀기
                    int ni = min(i + p[2], max_alp);
                    int nj = min(j + p[3], max_cop);
                    
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j] + p[4]);
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

실행 결과

 

코드 (다익스트라)

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

#define MAX 200

int dp[MAX][MAX];

int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = 0, max_cop = 0;
    for(auto p: problems) {
        max_alp = max(max_alp, p[0]);
        max_cop = max(max_cop, p[1]);
    }
    
    alp = min(alp, max_alp);
    cop = min(cop, max_cop);
    
    for(int i=alp; i<=max_alp; ++i) {
        for(int j=cop; j<=max_cop; ++j) {
            dp[i][j] = 1e6;
        }
    }
    
    priority_queue<tuple<int,int,int>> pq;
    
    dp[alp][cop] = 0;
    pq.push({0, alp, cop});
    
    while(!pq.empty()) {
        auto [time, cur_alp, cur_cop] = pq.top(); pq.pop();
        time = -time;
        
        if(cur_alp >= max_alp && cur_cop >= max_cop) return time;
        
        int next_alp = min(cur_alp + 1, max_alp);
        if(dp[next_alp][cur_cop] > time + 1) {
            dp[next_alp][cur_cop] = time + 1;
            
            pq.push({-(time+1), next_alp, cur_cop});
        }
        
        int next_cop = min(cur_cop + 1, max_cop);
        if(dp[cur_alp][next_cop] > time + 1) {
            dp[cur_alp][next_cop] = time + 1;
            
            pq.push({-(time+1), cur_alp, next_cop});
        }        
        
        for(auto p: problems) {
            if(cur_alp >= p[0] && cur_cop >= p[1]) {
                int next_alp = min(cur_alp + p[2], max_alp);
                int next_cop = min(cur_cop + p[3], max_cop);
                
                if(dp[next_alp][next_cop] > time + p[4]) {
                    dp[next_alp][next_cop] = time + p[4];
                    
                    pq.push({-(time+p[4]), next_alp, next_cop});
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

실행 결과