프로그래머스 문제 - 코딩 테스트 공부

프로그래머스 코딩 테스트 공부 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

코딩 테스트 문제를 풀기 위한 지식인 알고력과 코딩력이 있습니다.
특정 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.
1의 시간을 사용하여 알고력과 코딩력 중 한가지를 1 올릴 수 있습니다.
또는 특정 문제들을 풀어서 알고력과 코딩력을 올릴 수 있습니다.
주어진 알고력과 코딩력을 시작으로 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구해야합니다.
모든 문제들은 여려번 풀 수 있습니다.

문제 풀이

알고력과 코딩력을 문제를 통해 증가시켜 두 지식이 일정 이상 올라가도록 계산을 진행해야 합니다.

기본적으로 알고력과 코딩력을 1씩 올리는 것을 아무 조건없이 1의 시간을 투자하여 풀 수 있는 문제라고 생각하였을 때, 두 지식을 올리는 수단은 문제를 풀며 올리는 방법밖에 없습니다.

다른 최소한의 방법을 찾는 것보단 최악의 경우여도 계산양이 얼마 되지 않기 때문에 dp로 모든 값을 저장하며 최솟값을 찾아줍니다.

도달해야 하는 알고력과 코딩력을 알아낸 후 알고력이나 코딩력을 1 올리는 경우를 배열에 추가해줍니다.
이후 시작점은 cost를 0으로 맞춰준 후 풀 수 있는 문제의 cost값과 dp배열에 전에 저장한 cost값 중 적은 값을 저장해주며 진행합니다.
전부 계산을 진행 후 도달해야 하는 알고력과 코딩력의 dp배열 값을 return해주면 됩니다.

전체 코드

계산을 줄이는 방법보다 전부 검색하는 방법이 더 쉽고 빠른 경우가 있으니 문제를 해석할 때 좀 더 주의가 필요할 것 같습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    vector<vector<int>> dp(151, vector<int>(151, 2100000000));
    //도달해야하는 알고력과 코딩력
    int goal_alp = alp;
    int goal_cop = cop;
    
    for(int i = 0; i < problems.size(); i++)
    {
        goal_alp = max(goal_alp, problems[i][0]);
        goal_cop = max(goal_cop, problems[i][1]);
    }
    //아무 조건 없이 cost 1을 증가하여 알고력이나 코딩력 둘 중 하나를 올릴 수 있음
    problems.push_back({0, 0, 1, 0, 1});
    problems.push_back({0, 0, 0, 1, 1});
    
    //시작점은 cost 0
    dp[alp][cop] = 0;
    
    for(int i = alp; i <= goal_alp; i++)
    {
        for(int j = cop; j <= goal_cop; j++)
        {
            //목표값에 도달하면 계산할 필요 없음
            if(i == goal_alp && j == goal_cop)
                continue;
            
            int curCost = dp[i][j];
            
            //문제들을 현재 값과 더하며 최소로 되는 값을 검색
            for(vector<int> v : problems)
            {
                if(i < v[0] || j < v[1])
                    continue;
                
                //더해서 맞춰야하는 최대값보다 넘어가지 않도록 비교
                int nextAlp = min(goal_alp, i + v[2]);
                int nextCop = min(goal_cop, j + v[3]);
                
                if(dp[nextAlp][nextCop] > curCost + v[4])
                    dp[nextAlp][nextCop] = curCost + v[4];
            }
        }
    }

    answer = dp[goal_alp][goal_cop];
    
    return answer;
}

출저

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