[ALGORITHM] LEVEL3 2022 KAKAO TECH INTERNSHIP - 코딩 테스트 공부

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

프로그래머스

과정

1. 만족해야 하는 최대 알고력과 코딩력을 구한다.
2. 알고력 1, 코딩력 1 증가 문제를 추가한다.
3. 알고력과 코딩력을 x,y로 생각하고 방문 배열을 87'654'321로 초기화 해준다.
4. 다익스트라를 실행하되 최대 알고력과 코딩력을 넘어가지 않도록 해주고(방문 배열을 위해) 시간을 기준으로 우선순위 큐를 정렬한다.
5. 우선순위 큐를 사용하므로 항상 time값은 해당 알고력과 코딩값에 대한 최소 time이 된다. 만약 최대 알고력과 최대 코딩력을 큐에서 꺼낸 순간 만족한다면 무조건 최소값이 되므로 return time을 해준다.

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct dat{
    int time,alp,cop;
    
    bool operator<(const struct dat& d) const{
        return time > d.time;
    }
};

    
int mcost[151][151];
int maxalp = 0, maxcop = 0;

int dijkstra(int alp, int cop, vector<vector<int>> problems){
    priority_queue<dat> pq;
    
    fill(&mcost[0][0],&mcost[150][151],87654321);
    
    pq.push({0,alp,cop});
    mcost[alp][cop]=0;
    
    while(!pq.empty()){
        dat d=pq.top();
        
        pq.pop();
        
        if(d.time > mcost[d.alp][d.cop])
            continue;
        
        if(d.alp >= maxalp && d.cop >= maxcop)
            return d.time;
        
        for(int i=0,sz=problems.size();i<sz;++i){
            if(d.alp<problems[i][0]||d.cop<problems[i][1])
                continue;
            
            dat nd = {
                d.time+problems[i][4],
                d.alp+problems[i][2]>maxalp?maxalp:d.alp+problems[i][2],
                d.cop+problems[i][3]>maxcop?maxcop:d.cop+problems[i][3]
            };
            
            if(mcost[nd.alp][nd.cop] <= nd.time)
                continue;
            
            mcost[nd.alp][nd.cop]=nd.time;
            pq.push(nd);
        }
    }
    
    return -1;
}

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    
    for(int i=0,sz=problems.size();i<sz;++i){
        maxalp=max(maxalp,problems[i][0]);
        maxcop=max(maxcop,problems[i][1]);
    }
    problems.push_back({0,0,1,0,1});
    problems.push_back({0,0,0,1,1});
    
    answer=dijkstra(alp,cop,problems);
    
    return answer;
}