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

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다.

 

처음에는 다익스트라를 이용해서 문제를 풀었다. 다 맞혔으나 효율성 3번만 계속 시간 초과가 나왔다.

아직도 이유는 잘 모르겠다..

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 500
#define INF 1000000000

int dist[MAX + 1][MAX + 1];
vector<vector<int>> problems;
int maxAlgo = -1;
int maxCoding = -1;

void init()
{
    for (int y = 0; y <= MAX; y++)
    {
        for (int x = 0; x <= MAX; x++)
        {
            dist[y][x] = INF;
        }
    }
}

struct Node
{
    int algo;
    int coding;
};

struct Compare
{
    bool operator() (pair<Node, int>& a, pair<Node, int>& b)
    {
        if (a.second == b.second)
        {
            Node aNode = a.first;
            Node bNode = b.first;
            
            if (aNode.algo == bNode.algo)
            {
                return aNode.coding < bNode.coding;
            }
            return aNode.algo < bNode.algo;
        }
        return a.second > b.second;
    }
};

int solve(int startAlgo, int startCoding)
{
    dist[startAlgo][startCoding] = 0;
    priority_queue<pair<Node, int>, vector<pair<Node, int>>, Compare> pq;
    pq.push({{startAlgo, startCoding}, 0});
    
    int answer = INF;
    
    while (!pq.empty())
    {
        Node present = pq.top().first;
        int presentCost = pq.top().second;
        int algo = present.algo;
        int coding = present.coding;
        pq.pop();
        
        if (algo >= maxAlgo && coding >= maxCoding)
        {
            return presentCost;
        }
        
        // increase algo
        if (algo < maxAlgo && dist[algo + 1][coding] > presentCost + 1)
        {
            dist[algo + 1][coding] = presentCost + 1;
            pq.push({{algo + 1, coding}, presentCost + 1});
        }
        
        // increase coding
        if (coding < maxCoding && dist[algo][coding + 1] > presentCost + 1)
        {
            dist[algo][coding + 1] = presentCost + 1;
            pq.push({{algo, coding + 1}, presentCost + 1});
        }
        
        // solve problem
        for (vector<int>& problem : problems)
        {
            int algoReq = problem[0];
            int codingReq = problem[1];
            int algoRes = problem[2];
            int codingRes = problem[3];
            int cost = problem[4];

            if (algoRes == 0 && codingRes == 0)
            {
                continue;
            }
            if (codingRes == 0 && algo >= maxAlgo)
            {
                continue;
            }
            if (algoRes == 0 && coding >= maxCoding)
            {
                continue;
            }
            if (algo >= algoReq && coding >= codingReq)
            {
                int nextAlgo = algo + algoRes;
                int nextCoding = coding + codingRes;
                int nextCost = presentCost + cost;

                if (dist[nextAlgo][nextCoding] > nextCost)
                {
                    dist[nextAlgo][nextCoding] = nextCost;
                    pq.push({{nextAlgo, nextCoding}, nextCost});
                }
            }
        }
    }
    
    return -1;
}

int solution(int alp, int cop, vector<vector<int>> probs) 
{
    init();
    problems = probs;
    for (vector<int>& problem : problems)
    {
        int algoReq = problem[0];
        int codingReq = problem[1];
        int algoRes = problem[2];
        int codingRes = problem[3];
        int cost = problem[4];
        
        maxAlgo = max(maxAlgo, algoReq);
        maxCoding = max(maxCoding, codingReq);
    }
    int answer = solve(alp, cop);
    return answer;
}

위 코드는 효율성 3번이 풀리지 않는다.

 

따라서 다이나믹 프로그래밍을 떠올렸고, 탑 다운 방식으로 풀었으나 시간 초과가 나오는 경우가 많았다.

그래서 검색을 통해 바텀업 방식의 다이나믹 프로그래밍 코드를 발견했다.

 

여기서 내가 간과한 부분들이 있었는데, 처음 주어지는 alp, cop 가 max 보다 애초에 클 수가 있다는 점이다. 따라서 이미 만족할 경우 0을 처음부터 리턴해주어야 한다.

두번째로는 alp, cop 둘 중 하나만 max보다 큰 경우이다. 이 경우를 위해 max로 낮춰주는 연산이 들어가야 하고, 그 다음 dist[alp][cop]을 0으로 초기화해줘야 한다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 500
#define INF 2000000000

int dist[MAX + 1][MAX + 1];
vector<vector<int>> problems;
int maxAlgo;
int maxCoding;

void init()
{
    for (int y = 0; y <= MAX; y++)
    {
        for (int x = 0; x <= MAX; x++)
        {
            dist[y][x] = INF;
        }
    }
}

int solve(int algo, int coding)
{
    if (algo >= maxAlgo && coding >= maxCoding)
    {
        return 0;
    }
    if (algo >= maxAlgo)
    {
        algo = maxAlgo;
    }
    if (coding >= maxCoding)
    {
        coding = maxCoding;
    }
    dist[algo][coding] = 0;
    for (int i = algo; i <= maxAlgo; i++)
    {
        for (int j = coding; j <= maxCoding; j++)
        {
            dist[i + 1][j] = min(dist[i + 1][j], dist[i][j] + 1);
            dist[i][j + 1] = min(dist[i][j + 1], dist[i][j] + 1);   
            
            for (vector<int>& problem : problems)
            {
                int algoReq = problem[0];
                int codingReq = problem[1];
                int algoRes = problem[2];
                int codingRes = problem[3];
                int cost = problem[4];

                if (i >= algoReq && j >= codingReq)
                {
                    int nextAlgo = i + algoRes;
                    int nextCoding = j + codingRes;
                    int nextCost = dist[i][j] + cost;
                    
                    if (nextAlgo > maxAlgo)
                    {
                        nextAlgo = maxAlgo;
                    }
                    
                    if (nextCoding > maxCoding)
                    {
                        nextCoding = maxCoding;
                    }

                    dist[nextAlgo][nextCoding] = min(dist[nextAlgo][nextCoding], nextCost);
                }
            }
        }
    }
    
    return dist[maxAlgo][maxCoding];
}

int solution(int alp, int cop, vector<vector<int>> probs) 
{
    init();
    problems = probs;
    for (vector<int>& problem : problems)
    {
        int algoReq = problem[0];
        int codingReq = problem[1];
        
        maxAlgo = max(maxAlgo, algoReq);
        maxCoding = max(maxCoding, codingReq);
    }
    int answer = solve(alp, cop);
    return answer;
}