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

문제를 보고 접근방법을 고민하다가 DP로 접근해야될 거 같은 느낌은 들었는데 막상 풀려고 보니 쉽지는 않았고 카카오 해설블로그 글의 도움을 받아 풀이했다.

📜 문제 바로 가기 : 코딩 테스트 공부

제출코드

파이썬

def solution(alp, cop, problems):
    # 달성해야 되는 능력
    ma, mc = 0, 0
    for ra, rc, ga, gc, t in problems:
        ma, mc = max(ra, ma), max(rc, mc)
    
    
    N, M = 151, 151

    inf = 9999999999999
    DP = [[inf] * M for _ in range(N)] # 알고력 i, 코딩력 j 달성할 수 있는 최소 비용
    
    alp = min(alp, ma)
    cop = min(cop, mc)
    
    DP[alp][cop] = 0
    
    for i in range(alp, N):
        for j in range(cop, M):
            if i+1 < N:
                DP[i+1][j] = min(DP[i+1][j], DP[i][j] + 1)
            if j+1 < M:
                DP[i][j+1] = min(DP[i][j+1], DP[i][j] + 1)
            
            for ra, rc, ga, gc, t in problems :
                if i >= ra and j >= rc:
                    na, nc = min(ma, i+ga), min(mc, j+gc)
                    DP[na][nc] = min(DP[na][nc], DP[i][j] + t)
    
    
    ans = DP[ma][mc]

    return ans

---

접근방법

DP[i][j]의 값은 i의 알고력, j의 코딩력을 갖추기 위한 최소 비용을 나타낸다.

어떤 문제의 요구 알고력과 코딩력은 각각 150을 넘을 수 없으니 배열의 크기는 151을 주었다. 물론 실제로는 그냥 넘어가서 답이 나오는 경우가 있는데
na, nc = min(ma, i+ga), min(mc, j+gc)
이 부분을 이용해서 ma, mc (최대 알고력, 최대 코딩력)이 넘어가지 않도록 맞춰주었다.

한 가지 놓쳐서 정말 힘들었던 부분이

alp = min(alp, ma)
cop = min(cop, mc)

이 부분이다.
처음 내가 가지고 있는 능력 보다 문제에서 요구하는 최대 능력이 낮은 경우가 있어서 고려해줘야하는데, 이는 DP배열 값을 채워나갈때 이 값을 초기값 0으로 잡고 이후의 범위부터 탐색하며 찾기 때문에 이러한 처리가 필요하다.