2022 KAKAO TECH INTERNSHIP - 코딩 테스트 공부 (파이썬) 문제 및 풀이

문제

programmers.co.kr/learn/courses/30/lessons/118668
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

풀이

동적 계획법으로 풀이해야, 효율성 테스트를 통과할 수 있는 문제입니다. 각각의 코딩려과 알고력을 momoization하여 dp배열을 방문합니다. 코딩력을 1 높일 경우, 알고력을 1 높일 경우, 문제를 해결할 경우에 대하여 재귀적으로 방문합니다.

dp[alp][cop]: alp의 알고력과 cop의 코딩력을 얻는 최단 시간

코드

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

INF = 987654321
dp = [[-1] * 200 for _ in range(200)]
problems = []
max_alp = -1
max_cop = -1

def solve(alp, cop):
	# 각각 최대 코딩력에 도달했을 때
    if alp >= max_alp and cop >= max_cop:
        return 0
        
	# 이미 방문했다면
    if dp[alp][cop] != -1:
        return dp[alp][cop]

    dp[alp][cop] = INF
    
	# 코딩력 1 증가
    dp[alp][cop] = min(solve(min(max_alp, alp + 1), cop) + 1, solve(alp, min(max_cop, cop + 1)) + 1)
    
    # 각 문제 해결
    for i in range(len(problems)):
    	# 문제를 풀 수 있을 경우
        if alp >= problems[i][0] and cop >= problems[i][1]:
            dp[alp][cop] = min(dp[alp][cop], solve(min(max_alp, alp + problems[i][2]), min(max_cop, cop + problems[i][3])) + problems[i][4])
    return dp[alp][cop]

def solution(alp, cop, problem):
    global max_alp, max_cop
    global problems
    problems = problem
    global  dp

    for i in range(len(problems)):
        max_alp = max(max_alp, problems[i][0])
        max_cop = max(max_cop, problems[i][1])

    return solve(alp, cop)

회고

global 변수를 조심합시다.