코딩 테스트 공부

⭐️
def solution(alp, cop, problems):
    answer = -1
    INF = 987654321
    # 최대 alp, cop 구하기
    maxAlp, maxCop = -1, -1
    for pr in problems:
        maxAlp = max(maxAlp, pr[0])
        maxCop = max(maxCop, pr[1])
    alp, cop = min(alp, maxAlp), min(cop, maxCop)
    graph = [[INF for _ in range(maxCop+1)] for _ in range(maxAlp+1)]
    problems = sorted(problems, key=lambda x : (x[0], x[1]))
    
    # 초기화
    count = 0
    for i in range(alp, maxAlp+1):
        graph[i][cop] = count
        count += 1
    count = 0
    for i in range(cop, maxCop+1):
        graph[alp][i] = count
        count += 1
    
    # 행 순회하면서 dp배열 채우기
    for i in range(alp, maxAlp+1):
        for j in range(cop, maxCop+1):
            # 직전 칸에서의 문제해결, 독학, 직전 칸으로부터 독학 중 가장 작은 값으로 갱신
            if i+1 <= maxAlp:
                graph[i+1][j] = min(graph[i+1][j], graph[i][j]+1)
            if j+1 <= maxCop:
                graph[i][j+1] = min(graph[i][j+1], graph[i][j]+1)
            
            for pb in problems:
                if i >= pb[0] and j >= pb[1]:
                    nextAlp, nextCop = min(maxAlp, i+pb[2]), min(maxCop, j+pb[3])
                    graph[nextAlp][nextCop] = min(graph[nextAlp][nextCop], graph[i][j]+pb[4])
            
    return graph[maxAlp][maxCop]

---

2022 KAKAO TECH INTERNSHIP

우선 문제를 첫번째 봤을 때, dp 생각을 못했다.

하지만 알고력, 코딩력 2가지의 척도가 있고 시간에 따라 계속해서 작은 값을 유지해야 하기 때문에 이차원 배열의 dp를 생각하는게 자연스러웠다.
이 부분이 이 문제에서 얻어갈 첫번째 아이디어이다.

그런데 dp를 생각했음에도 불구하고 한참동안 풀지 못했는데, 그 이유는 dp 배열을 초기화하는 방향을 착각해서 였다.

행 방향 오름차순, 그리고 열 방향 오름차순으로 순회할 때 지금 보고 있는 칸을 전 칸에서 불러와 비교하는 것이 아니라,
갈 수 있는 다음 칸의 값을 미리 갱신해두고 후에 min 비교를 하는 방식으로 해야 한다.

알고력(alp), 코딩력(cop) 이 주어질 때 항상 0,0 으로 주어지는 것이 아니기 때문에 그 전 값들은 모두 초기화 된 값으로 존재하는데, 이 값들을 불러와 값 비교를 하는 과정에서 꼬일 수 있기 때문이다.

그리고 마지막, 주어진 alp 와 cop 값이 problems에 존재하는 max 값보다 클 경우가 있기 때문에 alp, cop 값을 조정해주어야 한다.

이 부분을 생각 못했기에 마지막 3~4개의 테스트 케이스를 고치는데 애먹었다..

아무튼, 이런 류의 문제를 읽으면 우선 dp로 풀어야 겠다! 고 생각을 해야 한다.

구현이기는 하지만, 그리디로 전혀 될 것 같은 느낌이 안들고 딱히 생각나는 알고리즘이 없다면... 사실 무조건 dp로 푸는게 효율성 측면에서도 좋다.

---

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