2022 KAKAO TECH INTERNSHIP 풀이

Level 1 - 성격 유형 검사하기 풀이
Level 2 - 두 큐 합 같게 만들기 풀이
Level 3 - 코딩 테스트 공부 풀이
Level 3 - 등산코스 정하기 풀이
Level 4 - 행렬과 연산 풀이

프로그래머스 - 코딩 테스트 공부 링크
(2022.10.26 기준 Level 3)

문제

문제마다 (필요 알고력, 필요 코딩력, 얻는 알고력, 얻는 코딩력, 푸는 시간)이 있고, 시간 1을 사용해서 알고력이나 코딩력을 1 얻는 공부가 있다. 모든 문제를 풀기 위한 알고력과 코딩력을 높이는 최소 시간

알고리즘

이런 느낌의 DP로 풀 수 있겠다만은, 난 바로 생각난 다익스트라로 풀었다.

풀이

알고력과 코딩력은 최대 150이다. 그러면 딱 2차원 다익스트라가 아닌가?

먼저 problems를 정리해야 한다.
공부는 시간 1을 소모해서 알고력이나 코딩력 1을 얻는다. 그렇다면 필요한 두 능력은 0, 푸는 시간은 1인 문제와 같다고 보면 된다.
그러므로 problems에 [0, 0, 1, 0, 1]과 [0, 0, 0, 1, 1] 두 공부를 문제로 생각하여 넣어서 오름차순으로 정렬하자.
정렬하는 이유는 나중에 다익스트라를 돌릴 때 정렬을 해놓게 되면, 더 이상 문제들을 탐색할 필요가 없어지는 시점을 만들 수 있다. 바로 현재 알고력과 코딩력이 필요한 알고력과 코딩력에 비해 전부 부족한 시점. 이 시점부터 나오는 문제들은 어차피 못푼다고 생각하고 탐색 중단하면 시간 최적화가 된다.

이쯤되면, 어떻게 다익스트라를 돌릴지 다 알 것이다.
현재 알고력과 코딩력의 거리(시간)과 (특정 문제를 풀 때의 다음 알고력과 코딩력의 거리(시간) + 특정 문제를 푸는 시간)을 비교하여 풀지 안풀지 결정하면서 distance 행렬을 채워가면 된다.

이 때, 중요한 점이 있다.
먼저, 달성하고자 하는 알고력과 코딩력. 즉, 문제들의 알고력과 코딩력의 각 최댓값을 구해놓는다. 그 값으로 행렬의 크기를 정해야 한다. 그리고 언제나 그 범위를 벗어나면 안된다.
만약 달성하고자 하는 코딩력이 150이고 현재 코딩력은 149, 풀어서 얻게 되는 코딩력은 2라고 생각해보자. 그렇다면 다음 코딩력은 151이 되는데 150이나 151이나 차이가 있는가? 어차피 달성하고자 하는 코딩력은 넘어서 의미가 없게 된다. 그러므로 min 연산으로 범위를 벗어나게 하지 말자.

주의사항

내가 맞왜틀한 이유인데, 처음에 주어지는 초기 알고력과 코딩력이 달성하고자 하는 알고력과 코딩력을 넘는 경우가 있다. 그래서 런타임 에러가 떴는데, 성하고자 하는 알고력과 코딩력을 구했으면 초기 알고력과 코딩력도 min 연산을 해주자.

코드

import heapq
from math import inf

def solution(alp, cop, problems):
    # 시간 1을 소모해서 알고력 1이나 코딩력 1을 올려주는 공부를 문제라고 생각하자.
    problems += [[0, 0, 1, 0, 1], [0, 0, 0, 1, 1]]
    problems.sort()

    # 모든 문제의 알고력과 코딩력의 각 최댓값
    goal_alp = problems[-1][0] # 알고력 최대
    goal_cop = 0 # 코딩력 최대
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        goal_cop = max(goal_cop, cop_req)

    # 알고력과 코딩력을 각 행과 열로 하여금 2차원 다익스트라
    # 현재 능력이 달성하고자 하는 알고력과 코딩력을 이미 넘어 있을 수 있다.
    alp = min(alp, goal_alp)
    cop = min(cop, goal_cop)
    queue = [[0, alp, cop]]
    distance = [[inf] * (goal_cop + 1) for _ in range(goal_alp + 1)] # 거리
    distance[alp][cop] = 0

    while queue:
        d, alp, cop = heapq.heappop(queue)
        if distance[alp][cop] < d:
            continue
        for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
            # 현재 두 능력이 필요한 두 능력보다 전부 부족하면 더 이상 탐색할 필요가 없다.
            # 하나만 부족하면 continue
            if alp < alp_req or cop < cop_req:
                if alp < alp_req and cop < cop_req:
                    break
                continue

            # 이 문제를 풀게 될 때 다음 알고력과 코딩력
            # 범위를 벗어나지 않게 하자.
            nxt_alp = min(alp + alp_rwd, goal_alp)
            nxt_cop = min(cop + cop_rwd, goal_cop)

            # 거리 계산 및 비교
            if distance[nxt_alp][nxt_cop] > distance[alp][cop] + cost:
                distance[nxt_alp][nxt_cop] = distance[alp][cop] + cost
                heapq.heappush(queue, [distance[nxt_alp][nxt_cop], nxt_alp, nxt_cop])

    return distance[goal_alp][goal_cop]

여담

시간 나면 dp로도 풀어봐야겠다.