[프로그래머스] 코딩 테스트 공부, python

https://school.programmers.co.kr/learn/courses/30/lessons/118668?language=python3

프로그래머스

 

모든 문제를 해결하기 위해 알고력과 코딩력의 최댓값을 계산한다.

 

dp [i][j]는 알고력이 i, 코딩력이 j에 도달하기까지의 최소 시간을 저장한다.

dp [현재 알고력+증가 알고력][현재 코딩력+증가 코딩력]에  d dp[현재 알고력+증가 알고력][현재 코딩력+증가 코딩력] 과 dp [현재 알고력][현재 코딩력]+걸린시간 중 최솟값을 갱신한다.

 

만약 현재 알고력+증가 알고력 또는 현재 코딩력+증가 코딩력이 최대 알고력, 최대 코딩력을 넘으면 dp배열 인덱스를 넘어서지 않게 알고력 최댓값, 코딩력 최댓값으로 넣어주었다.

 

def solution(alp, cop, problems):
    answer = 10**16

    maxalp = alp
    maxcop = cop
    
    # 1의 시간을 소모하여 1을 올리는 케이스도 추가해준다
    problems.append([0,0,1,0,1])
    problems.append([0,0,0,1,1])   
    
    # 최대 alp와 cop를 구한다
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        maxalp = max(maxalp, alp_req)
        maxcop = max(maxcop, cop_req)
        
    
    # dp[i][j] 는 alp가 i, cop가 j가 되는 최소 시간
    dp = [[10**16]*(maxcop+1) for _ in range(maxalp+1)]
    dp[alp][cop] = 0
    
    for curalp in range(alp,maxalp+1):
        for curcop in range(cop,maxcop+1):
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if alp_req>curalp or cop_req>curcop:
                    continue
                    
                nextalp = maxalp if curalp+alp_rwd>maxalp else curalp+alp_rwd
                nextcop = maxcop if curcop+cop_rwd>maxcop else curcop+cop_rwd
                dp[nextalp][nextcop] = min(dp[nextalp][nextcop],dp[curalp][curcop]+cost)
    
    
    answer = dp[maxalp][maxcop]
    
    return answer