풀이
[문제 풀이]
이 문제는 모든 문제를 풀기 위한 알고력과 코딩력을 상승시키고, 이때 최소 시간을 구하는 문제다.
여기서 문제를 풀기 위해서는 문제에서 요구하는 알고력과 코딩력을 만족해야 하므로, 모든 문제를 풀기 위해서는 각 문제에서 요구하는 알고력과 코딩력의 값 중 가장 큰 값 이상으로 능력을 올리면 된다.
여기서 최소 시간을 구해야 하는데 DP를 이용하면 쉽게 풀 수 있다.
특정 수치의 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구하면, 이 최소 시간을 이용해 다른 특정 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구할 수 있기 때문이다.
(즉, 작은 문제를 해결하는 것으로 전체 문제를 해결할 수 있기 때문에 DP를 이용하면 된다.)
이제 문제에서 특정 알고력 a와 코딩력 b를 가지고 있을 때 최소 공부시간이 c라고 하자.
이 최소 시간을 이용해 알고력과 코딩력을 늘리는 방법은 아래와 같다.
1. 1시간 공부해서 알고력을 1 올린다.
2. 1시간 공부해서 코딩력을 1 올린다.
3. 문제를 풀 수 있다면 문제를 풀어 알고력과 코딩력을 상승시키고 문제에서 요구하는 공부 시간만큼 공부한다.
이후 알고력과 코딩력이 향상되었으므로, 향상 된 알고력과 코딩력을 가진 상태를 다시 갱신해 최소 공부시간이 저장 되도록 한다.
+어차피 모든 문제를 풀기 위한 알고력과 코딩력의 max값은 정해져 있다.
그러므로 문제를 해결해 알고력이나 코딩력이 max값을 넘어가면 max값이라고 가정하고 비교하면 편하다.
[아이디어 정리]
- 특정 알고력과 코딩력을 갖고 있을 때, 최소 공부시간을 저장할 2차원 vector를 만든다.
- 특정 알고력과 코딩력을 가진 상태에서 능력을 올리는 방법은 문제를 풀어 올리는 방법과, 공부를 해 1시간에 1의 능력을 올리는 방법이 있다. 이 경우들을 적용해 상승시킨 알고력과 코딩력에 해당하는 최소 공부시간을 갱신한다.
- 최종적으로 계산이 끝났다면, 문제를 다 풀기 위해 필요한 max알고력과 max 코딩력일 때 공부시간을 return한다.
Code
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int alp, int cop, vector<vector<int>> problems) {
int answer = 0;
int maxCo=cop, maxAl=alp;
for (int i=0; i<problems.size(); i++) //모든 문제를 풀기 위한 알고력 코딩력
{
maxAl=max(maxAl,problems[i][0]);
maxCo=max(maxCo,problems[i][1]);
}
vector<vector<int>>DP(maxAl+1,vector<int>(maxCo+1,30000));
DP[alp][cop]=0; // 초기 위치
for (int i=alp; i<=maxAl; i++)
{
for (int j=cop; j<=maxCo; j++)
{
// co, al +1하는 경우
if (i<maxAl)
{
DP[i+1][j]=min(DP[i+1][j],DP[i][j]+1);
}
if (j<maxCo)
{
DP[i][j+1]=min(DP[i][j+1],DP[i][j]+1);
}
for (int k=0; k<problems.size(); k++)
{
if (i>=problems[k][0] && j>=problems[k][1])
{
int pAl=min(maxAl,i+problems[k][2]);
int pCo=min(maxCo,j+problems[k][3]);
DP[pAl][pCo]=min(DP[pAl][pCo],DP[i][j]+problems[k][4]);
}
}
}
}
return DP[maxAl][maxCo];
}
나도 1시간 공부했으니 알고력이1 상승했나...?
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C++] 기지국 설치 (0) | 2024.03.05 |
---|---|
[프로그래머스/C++] 억억단을 외우자 (0) | 2024.03.05 |
[프로그래머스/C++] 단어 퍼즐 (0) | 2024.03.03 |
[프로그래머스/C++] 짝수 행 세기 (0) | 2024.02.29 |
[프로그래머스/C++] 모두 0으로 만들기 (0) | 2024.02.27 |