⚙️ 알고리즘 분류 : DP
🔠 언어 : c++
🤫 힌트.
세 가지 경우로 나누어서 생각해라!
✏️ 풀이.
문제 풀이 단계
1) 준비 - 가장 큰 alp_req, cop_req를 구한다. 초기 alp, cop 값을 가지는 dp를 0으로 초기화 한다.
➡️ 문제에서 구하자고 하는 것은 "모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간"이다.
➡️ dp[알고력][코딩력]==시간
2) (alp<=alp_mx, cop<=cop_mx) 값을 하나씩 증가시켜서 보며 각 알고력과 코딩력에 따른 dp 값을 계산한다. 3가지 케이스로 나누어서 계산한다.
2-1) 알고력이 1증가 - 문제 풀이 X. 그냥 점수 증가.
➡️ dp[알고력+1][코딩력]=min(dp[알고력+1][코딩력], dp[알고력][코딩력]+1)
2-2) 코딩력이 1증가 - 문제 풀이 X. 그냥 점수 증가.
➡️ dp[알고력][코딩력+1]=min(dp[알고력][코딩력+1], dp[알고력][코딩력]+1)
2-3) 문제를 풀어서 증가
➡️ dp[알고력+문제 알고력 보상][코딩력+문제 코딩력 보상]
=min(dp[알고력+문제 알고력 보상][코딩력+문제 코딩력 보상],
dp[알고력][코딩력]+문제 푸는 시간)
*** 가장 중요한 조건은 밑에 헤맨 부분의 (2) 참고.
⚠️ 헤맨 부분.
(1) 같은 문제를 여러번 풀 수 있는 걸 어떻게 해결하지?
➡️ dp[알고력][코딩력]을 매번 구할 때마다 problems를 순회한다.
예를 들어서 [초기 알고력 2, 초기 코딩력 2]이고 [알고력 1, 코딩력 2]을 받을 수 있는 문제가 있다고 치자.
dp[2][2] -> dp[3][4]->dp[4][6]...
dp[2][2]에서 해당 문제를 두 번 풀면 dp[4][6]의 값을 업데이트 할 수 있다.
dp[2][2]에서 해당 문제 2번 풀기 == dp[2][2]에서 1번, dp[3][4]에서 1번 풀기
따라서 매번 problems를 순회하는 것이 같은 문제를 여러 번 푸는 것과 같다.
(2) 외않되? - alp와 alp_mx의 관계
➡️ 채점하는데 자꾸 실패가 떴다. 그건 예외 조건을 처리해주지 않아서다.
alp_mx라는 이름 때문에 alp보다 항상 클 것이라 생각할 수 있지만, 그런 조건은 문제에 없다. 그래서 alp_mx가 초기 alp보다 작을 경우를 처리해야 한다.
코드 초반에만 해줘야 할 게 아니라, 매번 dp를 구할 때 처리해줘야 한다.
예를 들어서 [초기 알고력 2, 초기 코딩력 2]이고 [최대 알고력 1, 코딩력 4]이라고 치자. 그럼 알고력을 올릴 필요는 없지만, 코딩력을 올릴 필요는 있다!
1) 코드 초반에 처리해주지 않는다면 for(int alp=2; alp<=1; alp++)가 아예 실행되지 않는다.
2) 코드 초반에 처리해주고 매번 dp 구할 때 처리해주지 않는다면
for(int alp=1; alp<=1; alp++){ for(int cop=2; cop<=4; cop++) }
CASE 1. dp[2][2] -> dp[2][3] -> dp[2][4]
CASE 2. dp[1][3] -> dp[1][4] -> dp[1][5]
3) 코드 초반에 처리해주고 매번 dp 구할 때 처리해준다면
CASE 1. dp[1][2] -> dp[1][3] -> dp[1][4]
CASE 2. dp[1][3] -> dp[1][4] -> dp[1][4]
.... 왜지...? 왜 처리 안 해주면 틀리는 거지...?
안 해줘도 되지 않을까...? 이건 좀 더 생각해봐야겠다.
다른 곳 풀이에서는 그저 '최댓값을 넘길 경우 에러(시간 초과, 세그먼~) 제거를 위해 제한'이라서 써져있다. 근데 배열 크기를 늘리면 되지 않을까...?
👩🏻💻 코드.
#include <string>
#include <vector>
#define MX 999999999
using namespace std;
// dp의 최대 index 값은 150(req)+30(rwd)이다.
// 150으로 줘서 segmentation fault가 발생했다.
vector<vector<int>> dp(201, vector<int>(201, MX));
int solution(int alp, int cop, vector<vector<int>> problems) {
int answer = 0, alp_mx=0, cop_mx=0;
for(int i=0; i<problems.size(); i++){
alp_mx=max(alp_mx, problems[i][0]);
cop_mx=max(cop_mx, problems[i][1]);
}
// 예외 처리
alp=min(alp, alp_mx), cop=min(cop, cop_mx);
dp[alp][cop]=0;
int x_idx, y_idx;
for(int i=alp; i<=alp_mx; i++){
for(int j=cop; j<=cop_mx; j++){
// 예외 처리
x_idx=min(i+1, alp_mx), y_idx=min(j+1, cop_mx);
// CASE 1. 알고력 1 증가
dp[x_idx][j]=min(dp[x_idx][j], dp[i][j]+1);
// CASE 2. 코딩력 1 증가
dp[i][y_idx]=min(dp[i][y_idx], dp[i][j]+1);
// CASE 3. 문제 풀이
for(int k=0; k<problems.size(); k++){
int alp_req=problems[k][0], cop_req=problems[k][1], alp_rwd=problems[k][2], cop_rwd=problems[k][3], cost=problems[k][4];
if(i<alp_req || j<cop_req) continue;
// 예외 처리
x_idx=min(i+alp_rwd, alp_mx), y_idx=min(j+cop_rwd, cop_mx);
dp[x_idx][y_idx]=min(dp[x_idx][y_idx], dp[i][j]+cost);
}
}
}
return answer=dp[alp_mx][cop_mx];
}😎 후기.
보자마자 dp라는 감은 왔지만, 풀지 않았던 문제다.
다시 풀 때도 너무 막막했다. 고려해야 할 조건이 많은 것 같아서 '이걸 도대체 어떻게 처리해야하나...' 싶은 고민을 많이 했다.
dp라는 알고리즘 자체에서 많은 유형의 문제가 파생되기에, dp 문제만 보면 살짝 두렵다. '점화식 어떻게 짜지...' 뭐 이런 고민이 크다...
차근히 정리하면 될 문제긴 하지만, 아직은 조굼 어렵다~
