DP, 즉 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다고 하여 '기억하며 풀기'라고 불리기도 한다.
일반적인 재귀 방식 또한 DP와 매우 유사하지만 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 차이점이 있다.
값을 저장해두고 재사용 한다면 불필요한 계산을 반복할 필요가 없어 시간복잡도를 줄일 수 있다.
O(n^2) -> O(f(n))으로 개선(다항식 수준으로, 문제에 따라 다름.)
이 문제는 DP(Dynamic Programming: 동적 계획법)을 이용해서 풀어야 한다.
문제에서 최대 필요 alp와 cop를 변수에 넣어준다.
2-1. 처음부터 주어진 alp와 cop가 최대 필요 alp & cop보다 클 수도 있기 때문에 비교해준다.
주어진 alp, cop를 시작으로 최대 필요 alp, cop까지 for문을 돌린다.
3-1. alp나 cop가 부족할 경우 1씩 추가해주고, dp 값과 비교하여 더 작은 값을 dp에 넣어준다.
3-2. 문제를 풀 수 있을 경우 문제를 풀고, dp 값과 비교하여 더 작은 값을 dp에 넣어준다.
dp[최대 필요 alp][최대 필요 cop] 값을 return 해준다.
def solution(alp, cop, problems):
max_alp, max_cop = 0, 0
# 문제 풀이 2번
for a,b,c,d,e in problems:
max_alp = max(max_alp, a)
max_cop = max(max_cop, b)
INF = float('inf')
dp = [[INF] * (max_cop + 1) for _ in range(max_alp + 1)] # 문제 풀이 1번
# 문제 풀이 2-1번
alp = min(alp, max_alp)
cop = min(cop, max_cop)
dp[alp][cop] = 0
# 문제 풀이 3번
for i in range(alp, max_alp+1):
for j in range(cop, max_cop+1):
# 문제 풀이 3-1번
if i < max_alp:
dp[i+1][j] = min(dp[i][j] + 1, dp[i+1][j])
if j < max_cop:
dp[i][j+1] = min(dp[i][j] + 1, dp[i][j+1])
# 문제 풀이 3-2번
for a,b,c,d,e in problems:
if i >= a and j >= b:
next_alp, next_cop = min(max_alp, i+c), min(max_cop, j+d)
dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][j] + e)
# 문제 풀이 4번
return dp[max_alp][max_cop]