코딩테스트 연습 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부

solution.py

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

import math


def solution(alp, cop, problems):

    # 필요 능력 구하기
    alp_max = 0
    cop_max = 0
    for alp_req, cop_req, _, _, _ in problems:
        alp_max = max(alp_max, alp_req)
        cop_max = max(cop_max, cop_req)

    # 기본 학습능력 추가
    problems.append([0, 0, 1, 0, 1])
    problems.append([0, 0, 0, 1, 1])

    # 자주 사용하는 값은 미리 계산해 두자
    alp_max_1 = alp_max + 1
    cop_max_1 = cop_max + 1
    INF = math.inf

    # 초기능력이 이미 능가한 경우가 있다고 함
    alp = min(alp_max, alp)
    cop = min(cop_max, cop)

    # 초기배열
    dp = [[INF]*cop_max_1 for _ in range(alp_max_1)]
    dp[alp][cop] = 0

    def walk(dp, alp, cop, p):
        alp_req, cop_req, alp_rwd, cop_rwd, cost = p

        if alp < alp_req or cop < cop_req:
            return

        alp_jump = min(alp_max, alp + alp_rwd)
        cop_jump = min(cop_max, cop + cop_rwd)

        dp[alp_jump][cop_jump] = min(
            dp[alp_jump][cop_jump], dp[alp][cop] + cost)

    # gogo
    for a in range(alp, alp_max_1):
        for c in range(cop, cop_max_1):
            for p in problems:
                walk(dp, a, c, p)

    return dp[alp_max][cop_max]


print(solution(10, 10, [[10, 15, 2, 1, 2], [20, 20, 3, 3, 4]]))
assert solution(10, 10, [[10, 15, 2, 1, 2], [20, 20, 3, 3, 4]]) == 15
assert solution(0, 0, [[0, 0, 2, 1, 2], [4, 5, 3, 1, 2], [
                4, 11, 4, 0, 2], [10, 4, 0, 4, 2]]) == 13