주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 가진다는 말은, 주어진 Problems 배열에서 가장 높은 req_alp 와 req_cop 을 각각 알고력과 코딩력으로 가지는 것과 동일하다. 따라서, 해결해야하는 문제는 (초기 알고력, 초기 코딩력)상태로 시작해, (목표 알고력, 목표 코딩력)상태에 도달하는 최단 시간을 구하는 문제이다.
이때, 목표 알고력을 넘는 알고력이나, 목표 코딩력은 구현방법에 따라, 런타임 오류를 일으킬 수 있습니다.
목표 알고력을 넘는 알고력은 목표 알고력으로, 목표 코딩력을 넘는 코딩력은 목표 코딩력을 계산하도록 처리하는 것이 안전한 방법이다.
dp[i][j]: (알고력 i, 코딩력 j ) 상태에 도달하는데 필요한 최단 시간
이렇게, dp 배열을 정의하면 문제에서 요구하는 답은 dp[목표알고력][목표코딩력] 입니다.
dp[초기알고력][초기코딩력]=0 으로 기저 사례를 잡고, 나머지 dp 배열 값은 무한으로 초기화한 후, 다음과 같은 방법으로 dp 배열을 업데이트 합니다.
- 알고리즘을 공부하여 알고력을 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) - 문제 하나를 선택하여 알고력과 코딩력을 높이는 경우:
dp[i+alp_rwd][j+cop_rwd]=min(dp[i+alp_rwd][j+cop_rwd],dp[i][j]+cost)
초기 알고력 <=i<= 목표 알고력, 초기 코딩력 <= j <= 목표 코딩력인 모든 (i,j) 에 대해 dp[i][j] 값을 업데이트해야하므로, 시간복잡도는 O(목표알고력 * 목표코딩력 * (problems 배열의 길이)) 가 된다.
이 방법 외에도, 그래프로 모델링 하여 최단거리를 찾는 다익스트라 알고리즘으로 바꿔서도 해결할 수 있다.