[프로그래머스] 코딩 테스트 공부 (python)

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

프로그래머스

풀이 방법

처음에는 그리디 하게 풀 수 있는 방법이 있나 생각해 봤는데 복잡할 거 같아서 dp로 풀어야겠다고 생각했다.

dp로 풀기 위해 중복되는 계산이 뭔지 생각해 봐야 한다.

이차원 배열로 dp[알고력][코딩력] = cost 알고력과 코딩력을 가지는데 필요한 최소 시간으로 설정했다.

dp배열을 모든 문제를 푸는데 필요한 최대 알고력과 코딩력의 크기로 int max값으로 초기화했다.

dp의 배열의 크기가 필요한 최대 알고력과 코딩력으로 설정했으므로 만약 문제를 풀었을 때 현재 알고력과 코딩력에서 얻은 알고력과 코딩력을 더해주면 필요한 최대 알고력과 코딩력의 범위를 넘어서는 list index range error가 발생하므로 만약 얻은 알고력이나 코딩력이 최대 값을 벗어나면 최대 값으로 보정해 주는 과정이 필요하다 

또 이렇게 하는 이유는 만약 이미 최대 알고력을 만족했어도 코딩력이 부족해 문제를 풀었는데 푼 문제에서 잉여 알고력을 얻는 경우에도 시간 계산 시 다 같은 경우로 취급해 주어야 하므로 보정해 주는 과정이 필요하다.

 

import math

def solution(alp, cop, problems):
    max_alp, max_cop = alp, cop ## 모든 문제를 푸는데 필요한 알고력, 코딩력 정의
    
    for problem in problems: ## 문제 중 최대 알고력 코딩력 구하기
        max_alp = max(max_alp, problem[0])
        max_cop = max(max_cop, problem[1])       
    dp = [[float('inf')] * (max_cop+1) for _ in range(max_alp+1)] ## dp 배열 생성하기 최대값으로        
    dp[alp][cop] = 0; ## 초기 값 0 으로 초기화
    for i in range (alp, max_alp + 1):
        for k in range (cop, max_cop + 1):            
            if i < max_alp: ## 1시간을 사용해서 알고력을 높임
                dp[i+1][k] = min(dp[i+1][k], dp[i][k] + 1)
            if k < max_cop: ## 1시간을 사용햇 코딩력을 높임
                dp[i][k+1] = min(dp[i][k] + 1, dp[i][k+1])
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems: ## 풀 수 있는 문제를 푸는 경우
                if i >= alp_req and k >= cop_req:
                    next_alp, next_cop = i + alp_rwd, k + cop_rwd
                    if next_alp > max_alp: ## dp 배열 index 범위를 넘어가지 않도록 수정 또는 모든 문제를 푸는데 필요한 능력을 넘으면 같은 값으로 dp에 저장하기 위한 설정
                        next_alp = max_alp;
                    if next_cop > max_cop:
                        next_cop = max_cop;
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][k] + cost) ## 문제를 푸는 경우 계산해서 min값 계산
    
    answer = dp[max_alp][max_cop]
    return answer