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

문제

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

프로그래머스

풀이

알고력 코딩력을 증가시키는 방법은 3가지이다.

1.알고리즘을 공부  -> 알고력+1

2. 코딩을 공부 -> 코딩력 +1

3. 문제를 풀면 -> 알고력 +n, 코딩력 +n

3가지 경우의 수로 db를 이용해서 풀면된다.

처음주어진 알고력과 코딩력이 문제를 풀기위해 필요한 알고력과 코딩력보다 높을 수 있기 때문에

for문의 인덱스를 둘중의 더 작은 값으로 설정한다.

#include <string>
#include <vector>

using namespace std;

vector<vector<int>>dp(181,vector<int>(181,1000000));
int alp_p,cop_p,t;


int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    int pb_size = problems.size(); 
    int alp_max=0,cop_max=0;
    for(int i = 0;i<pb_size;i++){
        
            alp_max = max(alp_max, problems[i][0]);
            cop_max = max(cop_max, problems[i][1]);
        
    }
    //alp > alp_max, cop>cop_max일 수 있음
    dp[alp][cop]=0;
    dp[min(alp_max,alp)][cop]=0;
    dp[alp][min(cop_max,cop)]=0;
    dp[min(alp_max,alp)][min(cop_max,cop)]=0;
    
    //시작 인덱스를 min(alp_max,alp) 로 지정
    for(int i=min(alp_max,alp);i<=alp_max;i++){
        for(int j=min(cop_max,cop);j<=cop_max;j++){
            
            //알고리즘 공부해서 알고력 +1
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1);
            //코딩공부해서 코딩력 +1
            dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1);
            
            //문제 풀어서 둘다 +n (n>=0)
            for(int k=0; k < pb_size ;k++){
                //현재 알고력과 코딩력으로 풀 수 없는 문제는 스킵
               if(problems[k][0]>i || problems[k][1]>j)
                   continue;
                
               alp_p = problems[k][2];
               cop_p = problems[k][3];
               int x=min(i+alp_p, alp_max);
               int y =min(j+cop_p, cop_max);
                dp[x][y] = min(dp[x][y] , dp[i][j]+ problems[k][4] );
            }
        }
    }
    
    return answer= dp[alp_max][cop_max];
}