프로그래머스 - 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) / Level 3 / Python

문제 📋

코딩테스트 연습 - 코딩 테스트 공부

풀이 📝

def solution(alp, cop, problems):
    max_alp_req, max_cop_req = [0, 0]  # 목표값
    
    for problem in problems:
        max_alp_req = max(max_alp_req, problem[0])
        max_cop_req = max(max_cop_req, problem[1])
    
    dp = [[float('inf')] * (max_cop_req+1) for _ in range(max_alp_req+1)]
    
    alp = min(alp, max_alp_req)  # 둘중 하나라도 목표값을 넘어가면 안된다.
    cop = min(cop, max_cop_req)
    
    dp[alp][cop] = 0  # dp[i][j]의 의미 : 알고력 i, 코딩력 j을 도달 할 수 있는 최단시간
    
    for i in range(alp, max_alp_req+1):
        for j in range(cop, max_cop_req+1):
            if i < max_alp_req:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            if j < max_cop_req:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if i >= alp_req and j >= cop_req:
                    new_alp = min(i+alp_rwd, max_alp_req)  # 둘중 하나라도 목표값을 넘어가면 안된다.
                    new_cop = min(j+cop_rwd, max_cop_req)
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost)
                    
    return dp[max_alp_req][max_cop_req]

쉽지 않은 문제였다.
풀이에 실패하여 카카오 해설을 보고 다시 문제를 풀어보았다.
BFS로 풀어도 정확도 테스트는 통과 할 수 있으나
효율성 테스트를 통과하기 위해선 DP로 문제를 접근해야 한다.

DP로 문제을 풀기 위해서 DP 배열을 정의하고 점화식을 도출해내야 하는데
개인적으로 이 DP 배열을 정의하는 것부터 좀 난해했던 것 같다.

dp[i][j] 정의 : 알고력 i, 코딩력 j을 도달 할 수 있는 최단시간

위와 같이 dp배열을 정의 할 수 있고
dp[alp][cop] = 0 을 시작으로 dp배열을 채워나가면
O(목표 알고력 목표 코딩력 (problems 배열의 길이)) 의 시간복잡도가 걸리며 효율성 테스트를 통과 할 수 있다.
그 외에도 알고력과 코딩력이 목표 알고력과 목표 코딩력을 초과하지 않도록 계속 체크해줘야 했다.