https://school.programmers.co.kr/learn/courses/30/lessons/118668

처음 접근 방식 : 완전탐색

import math
def solution(init_alp, init_cop, problems):
    N=len(problems)
    
    answer=math.inf
    tar_alp,tar_cop=0,0
    
    for i in range(N):
        tar_alp=max(tar_alp,problems[i][0])
        tar_cop=max(tar_cop,problems[i][1])
    
    def find_possible_problems(alp,cop):
        can_be_solved=[]
        for i in range(N): # O(N) 매번 호출함 -> 매번 호출하지 않아도 될거 같긴함
            if problems[i][0]<=alp and problems[i][1]<=cop:
                can_be_solved.append(i)
        return can_be_solved
    
    def P(alp,cop,cost):
        # base-condition
        if alp>=tar_alp and cop>=tar_cop:
            return cost
        # PRUNING
        if cost>=answer:
            return math.inf
        result=math.inf
        result=min(result,P(alp+1,cop,cost+1))
        result=min(result,P(alp,cop+1,cost+1))
        able2solve=find_possible_problems(alp,cop)
        for index in able2solve:
            result=min(result,P(alp+problems[index][2],cop+problems[index][3],cost+problems[index][4]))
        return result
    
    answer = P(init_alp,init_cop,0)
    return answer
    

RecursionError: maximum recursion depth exceeded in comparison

근데 같은 상태를 재귀적으로 호출하는 과정에서, recursion limit exception이 터짐!

⇒ 중복제거는 DP로 가능한것을 떠올려야 했다!!

DP 구현 방법

• Top-down : 질문형 @lru_cache(None) 인데 이 문제의 경우 그래도 시간 초과났다. 그냥 DP는 bottom-up으로 하자.
• Bottom-up : 축적형

모범 답안

import math
def solution(init_alp, init_cop, problems):
    N=len(problems)
    
    max_alp=max(problem[0] for problem in problems)
    max_cop=max(problem[1] for problem in problems)
    
    init_alp = min(init_alp, max_alp)
    init_cop = min(init_cop, max_cop)
    
    
    def find_possible_problems(alp,cop):
        can_be_solved=[]
        for i in range(N): 
            if problems[i][0]<=alp and problems[i][1]<=cop:
                can_be_solved.append(i)
        return can_be_solved
    
    DP=[[math.inf]*(max_cop+1) for _ in range(max_alp+1)] # 1-based
    DP[init_alp][init_cop]=0
    for a in range(init_alp,max_alp+1):
        for b in range(init_cop,max_cop+1):
            if DP[a][b]==math.inf:
                continue
            if a+1<=max_alp:
                DP[a+1][b]=min(DP[a+1][b],DP[a][b]+1)
            if b+1<=max_cop:
                DP[a][b+1]=min(DP[a][b+1],DP[a][b]+1)
            for pindex in find_possible_problems(a,b):
                _,_,rwd_a,rwd_c,cost=problems[pindex]
                na=min(max_alp,a+rwd_a)
                nb=min(max_cop,b+rwd_c)
                DP[na][nb]=min(DP[na][nb],DP[a][b]+cost)
    
    
    
    return DP[max_alp][max_cop]