[프로그래머스] 코딩 테스트 공부 - 파이썬

2022 KAKAO TECH INTERNSHIP - 118668. 코딩 테스트 공부

[Lv. 3]

 

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

프로그래머스

 

풀이

보자마자.. DP로 접근해야 될 것 같은 문제라고 생각했다.

[백준] 2342. Dance Dance Revolution - 파이썬 과 비슷한 느낌으로, Bottom-Up으로 풀면 된다.

dp[alp][cop] => 특정 alp, cop를 달성하기 위한 최소 시간(cost)

 

def solution(alp, cop, problems):
    INF = 10**9
    max_alp, max_cop = 0, 0

    for p in problems:
        max_alp = max(max_alp, p[0])
        max_cop = max(max_cop, p[1])
        
    # 런타임 에러 해결    
    if alp > max_alp:
        alp = max_alp
    if cop > max_cop:
        cop = max_cop

    dp = [[INF]*(max_cop+1) for _ in range(max_alp+1)]
    dp[alp][cop] = 0

    # 현재 alp부터 필요 alp까지, 현재 cop부터 필요 cop까지의 dp 배열을 memoization을 이용해 채워 나감.
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1):
            if i < max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            if j < max_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)

            for p in problems:
                if i >= p[0] and j >= p[1]:
                    alp_n = i+p[2]
                    cop_n = j+p[3]
                    # 필요 범위(배열 범위 밖)으로 넘어가면, max값으로 줄여줌.
                    if alp_n > max_alp:
                        alp_n = max_alp
                    if cop_n > max_cop:
                        cop_n = max_cop
										
                    # 최솟값 최신화!
                    dp[alp_n][cop_n] = min(dp[alp_n][cop_n], dp[i][j]+p[4])
                    
    return dp[max_alp][max_cop]