프로그래머스 코딩 테스트 공부

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

프로그래머스

주어지는 알고력과 코딩력의 범위가 0 ~ 150으로 범위가 작기 때문에 완전탐색이 가능할 것 같았으나 완전탐색으로 어떻게 접근해야할지도 모르겠고 어차피 시간초과가 나게 되어있다.

DP로 풀어야하는 문제이며 DP로 풀어야겠다고 생각이 든 순간 굉장히 문제가 쉬워진다.

한가지 주의점은 주어진 문제들보다 애초에 알고력 또는 코딩력이 높은 경우의 수인데 이러한 경우의 수를 생각하지 못해서 꽤나 시간을 낭비했다...

def solution(alp, cop, problems):

    max_alp = 0
    max_cop = 0
    
    for a, b, c, d, e in problems:
        max_alp = max(max_alp, a)
        max_cop = max(max_cop, b)
        
    # 목표 알고력
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    
    INF = float('inf')
    dp = [[INF] * (max_cop + 1) for _ in range(max_alp + 1)]
    dp[alp][cop] = 0

    for i in range(alp,max_alp+1):

        for j in range(cop,max_cop+1):

            if (j+1) <= max_cop:
                dp[i][j + 1] = min(dp[i][j] + 1, dp[i][j+1])

            if (i+1) <= max_alp:
                dp[i+1][j] = min(dp[i][j] + 1, dp[i+1][j])

            # alp가 i
            for p_al, p_co, r_al, r_co, cost in problems:
                if i >= p_al and j >= p_co:
                    new_p_al = i + r_al
                    new_p_co = j + r_co

                    if new_p_al > max_alp: new_p_al = max_alp
                    if new_p_co > max_cop: new_p_co = max_cop

                    dp[new_p_al][new_p_co] = min(dp[i][j] + cost, dp[new_p_al][new_p_co])

    return dp[-1][-1]