[C++][프로그래머스] 코딩 테스트 연습 🔥

프로그래머스

 

📄 문제

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

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

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

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

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

알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

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

 

📝 풀이

#include <string>
#include <vector>
#include <algorithm>
#define MAX_VALUE 1000000

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    
    // dp의 인덱스 번호는 현재 알고력과 코딩력의 누적 cost
    vector<vector<int>> dp(152, vector<int>(152, MAX_VALUE));
    
    // 요구하는 코딩력과 알고력을 구하기
    int maxAlp = alp, maxCop = cop;
    for(vector<int>& problem : problems)
    {
        maxAlp = max(maxAlp, problem[0]);
        maxCop = max(maxCop, problem[1]);
    }
    
    // 만약 alp와 cop가 요구하는 값 이상이라면 0 리턴
    if(alp >= maxAlp && cop >= maxCop)
        return 0;
    
    dp[alp][cop] = 0; // 시작 부분은 0
    for(int i = alp; i <= maxAlp; ++i)
    {
        for(int j = cop; j <= maxCop; ++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(vector<int>& problem : problems)
            {
                // 문제를 풀기위한 최소 알고력, 코딩력이 있다면?
                if(i >= problem[0] && j >= problem[1])
                {
                    // 기존 점수와 문제에서 얻은 점수의 합이 maxAlp, maxCop을 넘지 못하게 방지
                    // maxAlp + 1, 2..도 어차피 같은 경우로, [maxAlp][maxCop]에 값을 쓰고, 인덱스 번호를 추가로 사용하지 않도록 최적화
                    int alpIdx = min(maxAlp, problem[2] + i);
                    int copIdx = min(maxCop, problem[3] + j);
                    
                    // 문제를 풀었을 때, cost를 비교하여 낮은 값으로 갱신
                    dp[alpIdx][copIdx] = min(dp[alpIdx][copIdx], dp[i][j] + problem[4]);
                }
            }
        }
    }
    
    // 정답 리턴
    return dp[maxAlp][maxCop];
}

• dp bottom-up 방식으로 문제를 해결합니다.
• dp의 인덱스 번호를 현재 alp, cop의 누적 cost로 사용합니다. dp의 크기는 152, 152를 초과하지 않습니다.
  • 그 이유는, 0 ≤ alp,cop ≤ 150 조건으로, alp, cop가 150을 초과하지 않게 clamp를 해줄 수 있기 때문입니다.
  • alp + n을 alp로 간주하여 문제를 해결할 수 있습니다.
• 3중 for문을 이용하여 접근합니다.
  • i와 j는 각각 alp, cop에서 시작하여 maxAlp, maxCop까지 반복합니다.
• 아래의 세가지 검사를 통해 dp를 갱신합니다.
  • 알고리즘 공부를 통해 cost를 1추가하여 alp를 1 증가시킵니다.
  • 코딩 공부를 통해 cost를 1추가하여 cop를 1 증가시킵니다.
  • 모든 problems를 검사하여 cost를 추가하여 alp와 cop를 증가시킵니다. 단, 현재 alp와 cop인 i, j가 이상이어야합니다.
• 모든 반복을 마치면, 정답을 리턴합니다.