문제
해당 링크에 방문하면 문제를 확인할 수 있습니다.
간단히 설명드리면, 주어진 모든 문제를 풀기 위해 필요한 알고력과 코딩력을 얻기 위해 드는 최소한의 시간을 구하는 문제입니다.
풀이
저는 이 문제를 dp로 풀이하였습니다. 2차원 배열을 사용하였으며 dp가 의미하는 것을 다음과 같이 지정해주었습니다.
dp[a][b] = 알고력 a, 코딩력 b를 얻기 위해 드는 최소한의 시간
우선 작성한 코드를 먼저 보여드리겠습니다.
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int dp[151][151];
pii req[101]; // 문제별로 요구하는 {알고력, 코딩력}
pii rwd[101]; // 해당 문제를 풀었을 때 얻게 되는 {알고력, 코딩력}
int cost[101]; // 해당 문제를 풀기위해 드는 비용(시간)
pii mx = {0 ,0}; // 모든 문제를 풀기 위해 필요한 최대 능력값 {알고력, 코딩력}
int problemSize; // 주어진 problems의 개수
int DP(int alp, int cop) {
if (alp >= mx.first && cop >= mx.second) return 0;
if (dp[alp][cop] != -1) return dp[alp][cop];
int ret = 1e9;
for(int i = 0; i < problemSize; i++) {
int sum = 0;
if (req[i].first > alp) sum += req[i].first - alp;
if (req[i].second > cop) sum += req[i].second - cop;
if (sum > 0) {
ret = min(ret, DP(min(150, max(alp, req[i].first)), min(150, max(cop, req[i].second))) + sum);
}
else {
if (min(150, alp + rwd[i].first) == alp and min(150, cop + rwd[i].second) == cop) continue;
ret = min(ret, DP(min(150, alp + rwd[i].first), min(150, cop + rwd[i].second)) + cost[i]);
}
}
return dp[alp][cop] = ret;
}
int solution(int alp, int cop, vector<vector<int>> problems) {
memset(dp, -1 ,sizeof(dp));
problemSize = problems.size();
for(int i = 0; i < problemSize; i++) {
req[i] = {problems[i][0], problems[i][1]};
rwd[i] = {problems[i][2], problems[i][3]};
cost[i] = problems[i][4];
mx = {max(mx.first, req[i].first), max(mx.second, req[i].second)};
}
return DP(alp, cop);
}
solution함수부터 설명드리겠습니다.
memset(dp, -1 ,sizeof(dp));
dp 2차원 배열을 -1로 초기화합니다. 이후 problems에서 담고 있는 정보들을 req, rwd, cost 배열에 따로 보관합니다. 이건 나중에 변수로 알아보기 편하게 하기 위해 해주었습니다.
mx에는 문제에서 필요로하는 알고력의 최대값과 코딩력의 최대값을 저장합니다.
이후 DP함수를 실행합니다.
if (alp >= mx.first && cop >= mx.second) return 0;
만약 필요한 알고력과 코딩력 이상을 얻는다면 return 0을 해줍니다.
DP함수에서 해당 값을 방문했는지에 대한 여부를 if (dp[alp][cop] != -1) 조건문으로 확인하여 이미 계산된 값이라면 해당 값을 바로 return합니다.
ret에는 절대 될 수 없는 임의의 큰수를 먼저 저장해줍니다. (1e9는 10억정도 됩니다.) 그러면서 최소 시간을 찾을 겁니다. 만약, i번째의 problem을 풀 수 없다면 sum만큼 부족한 능력을 채워야 합니다. 그게 아니라면, 해당 문제를 풀어서 코딩력과 알고력을 얻습니다.
그런데 여기서 생각해야 할 문제가 두가지 있습니다. 문제에서 주어진 제한사항을 보면 필요한 코딩력과 알고력의 max는 150입니다. 하지만 만약, 부족한 코딩력을 채우기 위해 이미 max를 채운 알고력을 계속 더해준다면 어떻게 될까요? 즉, 우리는 max가 150이 넘어가지 않도록 고려해주어야 합니다. 저는 min함수를 이용해 150보다 큰 수가 올 경우 150이 되게끔 해주었습니다. 그래서 DP(min(150, max(alp, req[i].first)), min(150, max(cop, req[i].second)) 식으로 다소 복잡하게(?) 생긴 코드가 나온겁니다.
두번째는 무한루프입니다. 예를 들어, 모든 문제를 풀기 위해 필요한 알고력과 코딩력을 {10, 5}라고 해봅시다. 그리고 현재까지 내가 갖고 있는 알고력과 코딩력을 {7, 5}라고 했을 때 부족한 능력은 코딩력이 아닌 알고력일겁니다. 그런데 만약, 코딩력만을 증가시킬 수 있는 문제를 푼다면 어떻게 될까요? 아마 같은 문제를 계속해서 풀게 될겁니다. 이러한 경우를 방지해주기 위해 조건문 if (min(150, alp + rwd[i].first) == alp and min(150, cop + rwd[i].second) == cop)을 사용하여 내가 얻은 값이 이미 기존값과 일치하다면 continue를 해주었습니다.
마치며
정말 오랜만에 알고리즘 문제를 풀었네요..! 고려해야 할 부분이 있어 삽질도 꽤 많이 한것 같습니다. 그래도 생각하는 과정은 나름 재밌었습니다ㅎㅎ🐤👍
