[프로그래머스/kakao] 코딩 테스트 공부 (DP) - Python

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

프로그래머스

 

kakao 의 공식 해설을 참고했다. 

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

 

[문제]

주어진 모든 문제를 풀기 위해서 필요한 '알고력', 과 '코딩력' 에 도달하기 까지 걸리는 최소 시간을 구하는 것이 요구 사항이다. 

즉 초기의 알고력, 코딩력 -> (필요한) max_알고력, max_코딩력 에 도달하는 경로를 찾아야 한다고 해석했다. 

[알고리즘 > DP]

주어진 문제들 리스트인 problems 에서 현재의 알고력, 코딩력으로 풀 수 있는 문제를 풀어서 알고력과 코딩력을 높여야 한다. 그런데 어떤 문제를 푸는 것이 '최소 시간' 에 도달할지 알기 위해서 모든 경우를 따져봐야 한다고 생각했다. 이 모든 경우를 효율적으로 살펴보기 위해서 DP 알고리즘을 사용한다. 

[풀이]

1. max_alp 와 max_cop 를 구한다. 

problems 배열을 순회해서 최대로 필요한 알고력, 코딩력을 구한다. 

2. min_alp, min_cop 를 구한다. 

dp 한판을 완성하기 위해서 어디서 부터 순회할 것인지를 정해야 한다. 따라서 출발 지점이 되는 알고력, 코딩력을 구해야 한다. 

3. dp 한판을 완성한다 min_alp, min_cop 에서 max_alp, max_cop 로 이중 for 문으로 모든 칸을 순회한다. 

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

# dp[i][j] 에서 i == 알고력, j == 코딩력

1) 알고력 1 높이면 시간이 1 소요되는 것 으로 dp 칸을 채운다. 

dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)

2) 코딩력 1 높이면 시간이 1 소요되는 것으로 dp 칸을 채운다. 

dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)

3) problems 배열에서 풀 수 있는 문제를 하나 선택하여 알고력과 코딩력을 높이기 

단, i >= alp_req이고 j >= cop_req 여야 문제를 풀 수 있다. 

여기서 nalp, ncop 처리를 해주는 부분은 dp 배열의 범위를 초과하는 경우를 예외처리하기 위함이다. 또한 문제를 풀어서 얻는 알고력과 코딩력이 사실상 max_alp, max_cop 를 각각 초과하더라도 상관이 없으며 이 경우 소요되는 시간을 dp[max_alp][max_cop] 칸에 저장하면 된다! 

# problems list에서 문제 하나 선택하여 알고력 & 코딩력 높이기
# '최소 소요 시간' 인 경우 고르기

for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
    if alp_req <= i and cop_req <= j:
          nalp, ncop = min(max_alp, i + alp_rwd), min(max_cop, j + cop_rwd)
          dp[nalp][ncop] = min(dp[i][j] + cost, dp[nalp][ncop])

 

[전체 코드]

def solution(alp, cop, problems):
    INF = int(1e9)
    max_alp = 0 # 목표 알고력
    max_cop = 0 # 목표 코딩력
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems: 
        max_alp = max(max_alp, alp_req) # 최대 필요한 알고력 
        max_cop = max(max_cop, cop_req)

    alp, cop = min(max_alp, alp), min(cop, max_cop)
    dp = [[INF] * (max_cop+1) for _ in range(max_alp+1)]
    dp[alp][cop] = 0 # 초기 알고력, 코딩력 
    
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1): 
            # 알고력 1 높이기, 시간 1 소요 
            if i+1 <= max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            # 코딩력 1 높이기, 시간 1 소요 
            if j+1 <= max_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            
            # problems list에서 문제 하나 선택하여 알고력 & 코딩력 높이기 
            # '최소 소요 시간' 인 경우 고르기

            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems: 
                if alp_req <= i and cop_req <= j:
                    nalp, ncop = min(max_alp, i+alp_rwd), min(max_cop, j+cop_rwd)
                    dp[nalp][ncop] = min(dp[i][j] + cost, 
                                              dp[nalp][ncop])
    
    
    return dp[-1][-1] # 목표 알고력, 코딩력에 도달하기까지 걸리는 시간

 

풀 때마다 느끼지만 카카오 문제는 정말 고퀄이다.. 열공!