[2022 KAKAO TECH INTERNSHIP] 코딩 테스트 공부 dp

주의점

1. dp구성은 다음과 같다

dp[i][j] : 알고력이 i, 코딩력이 j를 얻기위해 걸리는 최소시간

 

2. 1시간 이후일 때

if now_alp != max_alp:
    dp[now_alp + 1][now_cop] = min(dp[now_alp][now_cop] + 1, dp[now_alp + 1][now_cop])
if now_cop != max_cop:
    dp[now_alp][now_cop + 1] = min(dp[now_alp][now_cop] + 1, dp[now_alp][now_cop + 1])

 

3. 문제를 이용할 때

* 문제를 통해 개선된 알고력과 코딩력이 max를 넘어가면 안되는것에 주의

for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
    if alp_req <= now_alp and cop_req <= now_cop:
        after_alp = min(max_alp, now_alp + alp_rwd)
        after_cop = min(max_cop, now_cop + cop_rwd)

        dp[after_alp][after_cop] = min(dp[after_alp][after_cop], dp[now_alp][now_cop] + cost)

 

4. 시작 알고력이 max알고력보다 크거나, 시작 코딩력이 max코딩력보다 클때 dp[alp][cop]=0에서 런타임 에러가 나므로 다음 코드가 필요하다.

alp = min(alp, max_alp)  # 시작 알고력과 코딩력이 max보다 많을 수 있다
cop = min(cop, max_cop)
dp = [[INF for j in range(max_cop + 1)] for i in range(max_alp + 1)]
dp[alp][cop] = 0

 

 

코드

def solution(alp, cop, problems):
    INF = 9876543210
    # 최대 알고, 구현 찾기
    max_alp, max_cop = 0, 0
    problems_size = len(problems)
    for i in range(problems_size):
        if problems[i][0] > max_alp:
            max_alp = problems[i][0]
        if problems[i][1] > max_cop:
            max_cop = problems[i][1]

    # dp[i][j] : 알고력i, 코딩력j를 얻기위해 걸리는 최소 시간
    alp = min(alp, max_alp)  # 시작 알고력과 코딩력이 max보다 많을 수 있다
    cop = min(cop, max_cop)
    dp = [[INF for j in range(max_cop + 1)] for i in range(max_alp + 1)]
    dp[alp][cop] = 0

    for now_alp in range(alp, max_alp + 1):
        for now_cop in range(cop, max_cop + 1):
            # 1시간 이후
            if now_alp != max_alp:
                dp[now_alp + 1][now_cop] = min(dp[now_alp][now_cop] + 1, dp[now_alp + 1][now_cop])
            if now_cop != max_cop:
                dp[now_alp][now_cop + 1] = min(dp[now_alp][now_cop] + 1, dp[now_alp][now_cop + 1])

            # 문제이용
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if alp_req <= now_alp and cop_req <= now_cop:
                    after_alp = min(max_alp, now_alp + alp_rwd)
                    after_cop = min(max_cop, now_cop + cop_rwd)

                    dp[after_alp][after_cop] = min(dp[after_alp][after_cop], dp[now_alp][now_cop] + cost)

    # for a in dp:
    #     print(a)

    return dp[-1][-1]