[Python] 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부

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

프로그래머스

 

이번 문제는 카카오 인턴십 문제로 출제된 코딩 테스트 공부이다! dp 문제는 언제나 구현하는 시간보다 생각하는 시간이 길어지는 것 같다. 

 

나는 항상 dp 문제와 그리디 문제를 헷갈려하는데, 풀 때 먼저 그리디 하게 풀려고 했을 때 직관적인 풀이가 잘 떠오르지 않으면 dp로 푸는 것 같다. 

 

코딩 테스트 공부 문제는 완전 탐색과 dp를 결합한 문제이다. 문제 요구 사항을 살펴보자. 

 

문제에서 초기 알고력, 코딩력이 주어지고 알고리즘 문제 리스트가 주어진다. 

알고리즘 문제는 다음과 같이 주어진다.
[문제를 풀기 위한 알고력, 문제를 풀기 위한 코딩력, 풀었을 때 오르는 알고력, 풀었을 때 오르는 코딩력, 푸는 데 걸리는 시간]
문제를 풀면 주어진만큼 알고력과 코딩력이 오르는데, 알고력과 코딩력은 공부를 해서 올릴 수 있다. 이때 시간을 1만큼 사용하면 알고력 또는 코딩력을 1만큼 올릴 수 있다. 문제를 여러 번 풀면 reward가 여러 번 적용된다. 

주어진 문제를 모두 풀기 위한 알고력과 코딩력을 갖추는데 걸리는 최소 시간을 구해라. 

 

문제를 처음 봤을 때는 냅색 문제를 떠올렸었다. 냅색 문제를 떠올려보면, 보통 한 가지를 최대화하면서 동시에 나머지 하나는 최소화하는 문제 유형이다. 이 문제도 마찬가지로 알고력과 코딩력을 올리는 동시에 시간은 최소화해야 한다. 

 

이러한 점을 고려하여, 나는 dp를 2차원 배열의 형태로 만들었다. 각각의 row와 column은 알고력과 코딩력을 의미하며, 문제에서 알고리즘 문제가 요구하는 최대 알고력과 코딩력은 각각 150으로 제한이 걸려있었기 때문에 배열의 크기는 151 x 151으로 설정했다. dp에 들어가는 값은 해당 (알고력, 코딩력)까지 도달하는데 걸리는 최소 시간을 의미한다. 따라서 처음에는 초기값을 제외하고는 모두 INF로 설정했다. 

 

이후 (0, 초기 알고력, 초기 코딩력)을 heapq에 넣은 후, 반복문을 돌면서 모든 경우를 계산해 주었다. 여기서 모든 경우란 현재의 알고력과 코딩력을 기반으로 풀 수 있는 문제들을 풀었을 때의 시간과 (알고력, 코딩력)을 계산하는 것을 말한다. 

 

반복문을 종료하는 조건은 힙이 비어있거나, 현재의 (알고력, 코딩력)이 모든 문제를 풀기에 충분한 정도일 때이다. 시간을 기준으로 힙에 삽입했기 때문에, 가장 처음으로 (알고력, 코딩력)이 모든 문제를 풀기 충분할 때가 가장 짧은 시간임을 보장할 수 있다. 

 

코드는 아래와 같다. 

 

import heapq

def solution(alp, cop, problems):
    INF = int(1e9)
    answer = INF
    
    max_alp = 0
    max_cop = 0
    
    for problem in problems:
        max_alp = max(max_alp, problem[0])
        max_cop = max(max_cop, problem[1])
    
    dp = [[INF] * 151 for _ in range(151)]
    dp[alp][cop] = 0
    
    h = []
    heapq.heappush(h, (0, -alp, -cop))
    problems += [[0, 0, 1, 0, 1], [0, 0, 0, 1, 1]]
    problems.sort()
    while h:
        time, alp, cop = heapq.heappop(h)
        alp *= -1 
        cop *= -1
        if max_alp <= alp and max_cop <= cop:
            answer = time
            break
        for problem in problems:
            if alp < problem[0]:
                break
            if cop < problem[1]:
                continue
            next_alp = alp + problem[2]
            next_cop = cop + problem[3]
            if next_alp > 150:
                next_alp = 150
            if next_cop > 150:
                next_cop = 150
            next_time = time + problem[4]
            if dp[next_alp][next_cop] > next_time:
                dp[next_alp][next_cop] = next_time
                heapq.heappush(h, (next_time, -next_alp, -next_cop))
    
    return answer