문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

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

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

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

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

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

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

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

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

제한사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

문제 풀이

처음 보는 dp 문제였다… 이전의 계산 결과를 다음의 계산에 활용한다는 dp의 개념 자체는 어렴풋이 알고 있었고 그런 개념과 유사한 문제를 몇개 풀어본 적은 있었지만 이렇게 제대로 된 dp문제를 풀게된 것은 처음이었다. 이렇게 문제의 유형 자체를 감을 잡지 못하는 경우는 잔머리를 굴려서 문제를 풀기는 정말 요원한 것 같다.
문제 자체는 다이나믹 프로그래밍 문제로 코딩력과 알고력의 최대 수치(150+rwd의 최대인 30)만큼의 2차원 배열 dp를 만들어서 우리가 가진 경우의 수

1. 코딩력을 올린다
2. 알고력을 올린다
3. 현재 풀 수 있는 문제 중 하나를 푼다

모두를 체크하며 dp의 수치를 갱신해나가면 되는 문제이다. 이렇게 보면 평범한 dp 문제이지만 이 문제가 어려운 이유는 문제가 요구하는 여러 예외처리에 있다.
첫째로 문제 최초 시점의 알고력이나 코딩력이 이미 요구 알고력이나 코딩력보다 높을 경우가 있다. 이 경우에는 함수에서 제대로 dp 배열을 갱신할 수 없으므로 처음에 min 함수를 사용하여 예외처리를 해주어야 한다.
두번째는 계산 도중 알고력과 코딩력의 값이 요구하는 알고력이나 코딩력보다 높아지는 경우이다. 우리는 정답인 최소 시간을 dp[요구알고력][요구코딩력]으로 구하게 되는데 문제를 풀거나 하여 알고력이 요구 알고력보다 높아지더라도 조건은 만족하는 것이 된다. 그리고 이 때의 시간이 요구 알고력을 딱 맞춰 달성했을 때보다 적게 걸릴 수 있으므로 이 또한 min함수로 현재의 알고력과 요구 알고력 중 작은 것을 값에 넣어야 제대로 된 정답을 얻을 수 있다.
이 문제를 계기로 앞으로 여러 dp 문제를 풀어보며 개념에 대한 감을 잡을 생각이다. 문제 유형은 많은데 점점 유형을 비트는 경우가 많아 더 어려워지는 추세인 것 같다.

코드

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> dp(180,vector<int>(180,10000)); //최대 시간으로 초기화된 180,180개의 2차원 배열 dp

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    int maxcop=0; int maxalp=0;
    for(vector<int> v : problems) {
        maxcop=max(maxcop,v[1]);
        maxalp=max(maxalp,v[0]);
    } //요구 알고력, 코딩력 저장
    alp=min(alp,maxalp); cop=min(cop,maxcop); //예외처리 1
    dp[alp][cop]=0; //현재 알고력=요구 알고력일 경우 0 반환
    for(int i=alp; i<=maxalp; i++) {
        for(int j=cop; j<=maxcop; j++) {
            int x=min(i+1, maxalp); int y=min(j+1, maxcop); //예외처리 2
            dp[x][j]=min(dp[x][j], dp[i][j]+1); //저장된 값과 현재+1중 작은것
            dp[i][y]=min(dp[i][y], dp[i][j]+1);
            for(vector<int> v : problems) {
                x=min(i+v[2], maxalp); y=min(j+v[3],maxcop);
                if(i<v[0] || j<v[1]) continue; //문제 요건 충족 불가 시 continue
                dp[x][y]=min(dp[x][y], dp[i][j]+v[4]);
            }
        }
    }
    return dp[maxalp][maxcop];
}