DP, 다익스트라

프로그래머스 2022 KAKAO TECH INTERNSHIP Level 3 문제 코딩 테스트 공부를 Java를 이용해 풀어보았다.
BFS를 이용해 Queue를 통해 풀어보려 했지만 도저히 안 돼서 찾아봤더니 보통은 DP와 다익스트라를 이용해서 풀었더라.

문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/118668

---

최소 비용 구하기

결국 문제의 본질은 가장 높은 기준의 문제를 풀기까지의 최소 비용을 구하는 것이다. 처음에는 이 컨셉을 BFS의 최단 거리 구하기로 생각해서 BFS 로 계속 쑤셔봤지만 풀면서도 뭔가 아니라는 생각이 들었다. 하지만 다른 방법이 달리 떠오르지 않아 계속 실패했다.

DP 배열 이용하기

맨 처음 주어진 능력치를 시작으로 가장 높은 조건을 만족시키는 지점까지 능력치 1씩 올라가며 모든 지점들에 대해 최소 비용을 갱신해나가며 bottom-up 방식으로 접근해야 한다.

그 과정에서 고려해야 할 것들이 몇 가지 있다.

1. 목표 지점을 이미 지나쳐버리게 능력치가 확 올라가는 경우는, 목표 능력치로 낮춰주는 작업이 필요하다. 그렇지 않으면 능력치 (10,10) 만 맞추면 되는 것을 (15,14) 등으로 넘어가버려서 실제 (10,10) 에 대한 접근을 건너 뛰어버리게 되기 때문이다.

2. 또한 문제를 풀이하는 경우가 아닌, 학습을 해서 알고력 혹은 코딩력을 1씩 올리는 경우에 대해서도 갱신해주어야 한다.

1에 대한 코드는 다음과 같다.

for(int i=alp; i<=alp_target; i++){
    for(int j=cop; j<=cop_target; j++){

        for(int p=0; p<problems.length; p++){
            if(i<problems[p][0] || j<problems[p][1])    continue; // 못 푸는 문제

            int nxt_alp = i + problems[p][2];
            int nxt_cop = j + problems[p][3];
            int nxt_cost = visit[i][j] + problems[p][4];

            if(nxt_alp>alp_target)  nxt_alp = alp_target;
            if(nxt_cop>cop_target)  nxt_cop = cop_target;

            visit[nxt_alp][nxt_cop] = Math.min(visit[nxt_alp][nxt_cop], nxt_cost);
        }
    }
}

2에 대한 코드는 다음과 같다.

for(int i=alp; i<=alp_target; i++){
    for(int j=cop; j<=cop_target; j++){
        visit[i+1][j] = Math.min(visit[i+1][j], visit[i][j]+1);
        visit[i][j+1] = Math.min(visit[i][j+1], visit[i][j]+1);
    }
}

그 외의 부분은 그냥 문제 설정 따라 초기화를 해주는 것만 신경 쓰면 된다. dp 배열은 처음엔 모두 INTEGER_MAX 와 같이 큰 수들로 초기화해두는 것만 기억하면 된다.

다음은 제출한 전체 코드다.

class Solution {
    final int INF = 2000000000;
    
    public int solution(int alp, int cop, int[][] problems) {
        int alp_target = 0, cop_target = 0;
        
        for(int[] prob: problems){
            alp_target = Math.max(alp_target, prob[0]);
            cop_target = Math.max(cop_target, prob[1]);
        }
        
        if(alp>=alp_target && cop>=cop_target)   return 0;
        if(alp>=alp_target) alp = alp_target;
        if(cop>=cop_target) cop = cop_target;
        
        int[][] visit = new int[alp_target+2][cop_target+2];
        
        for(int i=alp; i<alp_target+2; i++){
            for(int j=cop; j<cop_target+2; j++)
                visit[i][j] = INF;
        }
        visit[alp][cop] = 0;
        
        for(int i=alp; i<=alp_target; i++){
            for(int j=cop; j<=cop_target; j++){
                
                visit[i+1][j] = Math.min(visit[i+1][j], visit[i][j]+1);
                visit[i][j+1] = Math.min(visit[i][j+1], visit[i][j]+1);
                
                for(int p=0; p<problems.length; p++){
                    if(i<problems[p][0] || j<problems[p][1])    continue; // 못 푸는 문제
                                        
                    int nxt_alp = i + problems[p][2];
                    int nxt_cop = j + problems[p][3];
                    int nxt_cost = visit[i][j] + problems[p][4];
                    
                    if(nxt_alp>alp_target)  nxt_alp = alp_target;
                    if(nxt_cop>cop_target)  nxt_cop = cop_target;
                    
                    visit[nxt_alp][nxt_cop] = Math.min(visit[nxt_alp][nxt_cop], nxt_cost);
                }
            }
        }
        
        return visit[alp_target][cop_target];
    }
}

---

DP 배열 문제에 특히 취약한 것 같다. 작은 조각들을 하나씩 조립해서 큰 단위를 만드는 것에 대한 그림이 잘 안 그려지는 것 같다. 주어진 문제를 그냥 한 덩어리로 보기보다는, 분리해서 볼 수 있는 관점을 갖기 위해 머리를 그 방향으로 굴리도록 신경 써서 바라보자.