99클럽 코테스터디 42일차 TIL 프로그래머스- 코딩테스트 공부

코딩 테스트 공부

프로그래머스 Level 3 2022 KAKAO TECH INTERSHIP
문제 링크

프로그래머스

 

문제 설명

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 
코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 
알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.
풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 
알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 
각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.

문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 
문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 
모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

문제 풀이

Buttom-up 방식으로 풀이했다.
문제를 보며 고민하다가, 막막해서 답안을 보면서 문제를 풀었다.
2022 테크 여름인턴십 코딩테스트 해설

2022 테크 여름인턴십 코딩테스트 해설 - tech.kakao.com

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;

    int dp[160][160], MAXAlgo=0, MAXCoding=0;

    for (vector<int> v : problems) {
        MAXAlgo = max(MAXAlgo, v[0]);
        MAXCoding = max(MAXCoding, v[1]);
    }

    for (int i=0; i<=MAXAlgo; i++) {
        for (int j=0; j<=MAXCoding; j++) {
            dp[i][j] = 1e9;
        }
    }

    alp = min(alp, MAXAlgo);
    cop = min(cop, MAXCoding);

    dp[alp][cop]=0;
    for (int i=alp; i<=MAXAlgo; i++) {
        for (int j=cop; j<=MAXCoding; j++) {
            if (i < MAXAlgo) dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1);
            if (j < MAXCoding) dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1);
            for(auto v: problems) {
                if (i >= v[0] && j >= v[1]) {
                    int tmpAlp = min(i+v[2], MAXAlgo);
                    int tmpCop = min(j+v[3], MAXCoding);
                    dp[tmpAlp][tmpCop] = min(dp[tmpAlp][tmpCop], dp[i][j]+v[4]);
                }
            }
        }
    }

    return dp[MAXAlgo][MAXCoding];
}

Dijkstra 풀이

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct State {
    int alp, cop, cost;
    bool operator<(const State& other) const {
        return cost > other.cost;
    }
};

int solution(int alp, int cop, vector<vector<int>> problems) {
    int MAXAlgo = 0, MAXCoding = 0;

    for (vector<int> v : problems) {
        MAXAlgo = max(MAXAlgo, v[0]);
        MAXCoding = max(MAXCoding, v[1]);
    }

    alp = min(alp, MAXAlgo);
    cop = min(cop, MAXCoding);

    priority_queue<State> pq;
    vector<vector<int>> dist(160, vector<int>(160, 1e9));

    pq.push({alp, cop, 0});
    dist[alp][cop] = 0;

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        if (dist[current.alp][current.cop] < current.cost) continue;

        if (current.alp < MAXAlgo) {
            int newAlp = current.alp + 1;
            int newCost = current.cost + 1;
            if (newCost < dist[newAlp][current.cop]) {
                dist[newAlp][current.cop] = newCost;
                pq.push({newAlp, current.cop, newCost});
            }
        }

        if (current.cop < MAXCoding) {
            int newCop = current.cop + 1;
            int newCost = current.cost + 1;
            if (newCost < dist[current.alp][newCop]) {
                dist[current.alp][newCop] = newCost;
                pq.push({current.alp, newCop, newCost});
            }
        }

        for (auto& v : problems) {
            if (current.alp >= v[0] && current.cop >= v[1]) {
                int newAlp = min(current.alp + v[2], MAXAlgo);
                int newCop = min(current.cop + v[3], MAXCoding);
                int newCost = current.cost + v[4];

                if (newCost < dist[newAlp][newCop]) {
                    dist[newAlp][newCop] = newCost;
                    pq.push({newAlp, newCop, newCost});
                }
            }
        }
    }

    return dist[MAXAlgo][MAXCoding];
}

회고

DP는 아직도 보면 막막한 것 같다.
최근에 좋은 기회로 알고리즘 강의를 무료로 들을 수 있게 됐는데, 그걸 계기로 삼아봐야겠다.
이 문제는 DP 와 다익스트라 두 가지 방식으로 풀이할 수 있었는데, 시간적 측면에서는 다익스트라가 좀 더 나았다.