[Programmers] P118668 코딩 테스트 공부

[Programmers] P118668 코딩 테스트 공부

Question

Language: Python

알고력, 코딩력을 변수로 설정해서 이에 대한 DP 방식으로 접근한다.

dp=[[inf] * (req_cop+1) for _ in range((req_alp+1))]

알고 공부 및, 코딩 공부

#알고 공부
if i +1 <=req_alp:
    dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
#코딩 공부
if j +1 <=req_cop:
    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:
    #문제를 풀수 있는 조건이 만족되면, 저장되어 있는 cost와 비교해서 갱신
    if i>=alp_req and j >=cop_req:
        next_alp=min(req_alp,i+alp_rwd)
        next_cop=min(req_cop,j+cop_rwd)   
        dp[next_alp][next_cop]=min(dp[next_alp][next_cop],dp[i][j]+cost)

실수한 부분

해당 문제를 처음에는 recursion으로 접근해서 들어갔는데, 그렇게 하면 코딩 공부, 알고리즘 공부로 인해 재귀함수의 깊이가 상당히 싶어진다. 따라서, 이를 효율적으로 풀기 위해 DP 방식으로 접근해야한다.

–> 알고보면 간단한 DP 문제인데, 왜 재귀함수로 접근했을까…..

Solution

from math import inf
def solution(alp, cop, problems):
    req_alp,req_cop=0,0
    answer = 0
    #모든 문제를 풀기 위한 알고력, 코딩력 최소 요구량을 구한다.
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        req_alp=max(req_alp,alp_req)
        req_cop=max(req_cop,cop_req)
    
    #초기 알고력, 코딩력이 요구하는 알고력, 코딩력 보다 높을 수 있다
    alp=min(alp,req_alp)
    cop=min(cop,req_cop)
    
    #알고력, 코딩력에 관한 dp 배열 설정
    dp=[[inf] * (req_cop+1) for _ in range((req_alp+1))]
    #초기 알고력, 코딩력
    dp[alp][cop]=0
    
    for i in range(alp,req_alp+1):
        for j in range(cop, req_cop+1):
            
            #알고 공부
            if i +1 <=req_alp:
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
            #코딩 공부
            if j +1 <=req_cop:
                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:
                #문제를 풀수 있는 조건이 만족되면, 저장되어 있는 cost와 비교해서 갱신
                if i>=alp_req and j >=cop_req:
                    next_alp=min(req_alp,i+alp_rwd)
                    next_cop=min(req_cop,j+cop_rwd)   
                    dp[next_alp][next_cop]=min(dp[next_alp][next_cop],dp[i][j]+cost)
                          
    answer=dp[-1][-1]
    return answer