[Programmers] 118668번 - 코딩 테스트 공부 [Java][C++]

문제 링크

---

1. 아이디어

주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 쌓는 데 필요한 최단시간을 구하는 문제로 다이나믹 프로그래밍을 활용하면 효율적으로 해결할 수 있다. dp 테이블의 경우 dp[i][j]를 $i$ 의 알고력과 $j$ 의 코딩력을 쌓는 데 필요한 최단시간으로 정의하면 되며, 이때 주어진 문제 중 알고력의 상한을 alp_max, 코딩력의 상한을 cop_max라고 했을 때 dp[alp_max][cop_max]를 구하면 된다.

목표가 alp_max, cop_max이므로 그보다 높은 능력치는 아무 문제도 새로 풀어주지 못해 의미가 없다. 따라서 dp 테이블의 크기는 현재 능력치와 무관하게 주어진 문제들의 상한만으로 잡아줬고, 현재 알고력이나 코딩력이 이미 그 상한보다 높은 경우에는 상한까지 깎아 시작 위치로 삼아줬다. dp 테이블의 경우 무한대로 초기화한 후 기본 알고력과 코딩력은 보유하고 있으므로 해당 위치는 0으로 초기화해줬다.

dp 테이블 갱신은 현재의 알고력, 코딩력으로부터 미래의 알고력, 코딩력을 구해주는 방식으로 갱신했는데 1의 시간으로 알고력이나 코딩력을 1 올릴 수 있으므로 $dp[i + 1][j] = \min(dp[i + 1][j], dp[i][j] + 1)$, $dp[i][j + 1] = \min(dp[i][j + 1], dp[i][j] + 1)$ 이 된다. 또한 문제를 풀어서 알고력, 코딩력을 올릴 수 있는데 이를 위해 문제 리스트 중에서 현재 풀 수 있는 문제들을 필터링한 후 해당 문제를 푼 경우의 알고력, 코딩력을 쌓는 데 필요한 최단시간을 갱신해줬다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(A \cdot C \cdot P)$	$O(A \cdot C)$

$A$ = 모든 문제의 alp_req 최댓값, $C$ = 모든 문제의 cop_req 최댓값, $P$ = problems 개수

---

3. 코드

풀이 [Java][C++]

ni, nj를 보면 문제를 풀어 도달한 능력치와 alp_max, cop_max 중 작은 값을 취하는 것을 볼 수 있다. 보상을 그대로 더하면 dp 테이블의 범위를 넘어갈 수 있는데, 상한을 넘는 능력치는 어차피 의미가 없으므로 상한으로 깎아 같은 칸에 모아주면 범위 초과 없이 갱신할 수 있다.

import java.util.*;

class Solution {

    static int INF = 1_000_000_000;

    public int solution(int alp, int cop, int[][] problems) {
        int alp_max = 0;
        int cop_max = 0;
        for (int[] p : problems) {
            alp_max = Math.max(alp_max, p[0]);
            cop_max = Math.max(cop_max, p[1]);
        }
        alp = Math.min(alp, alp_max);
        cop = Math.min(cop, cop_max);

        int[][] dp = new int[1 + alp_max + 1][1 + cop_max + 1];
        for (int[] arr : dp) {
            Arrays.fill(arr, INF);
        }
        dp[alp][cop] = 0;

        for (int i = alp; i <= alp_max; i++) {
            for (int j = cop; j <= cop_max; j++) {
                dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);

                for (int[] p : problems) {
                    if (i < p[0] || j < p[1]) continue;

                    int ni = Math.min(i + p[2], alp_max);
                    int nj = Math.min(j + p[3], cop_max);
                    dp[ni][nj] = Math.min(dp[ni][nj], dp[i][j] + p[4]);
                }
            }
        }

        return dp[alp_max][cop_max];
    }
}

#include <algorithm>
#include <vector>

using namespace std;

const int INF = 1'000'000'000;
int dp[1 + 150 + 1][1 + 150 + 1];

int solution(int alp, int cop, vector<vector<int>> problems) {
    int alp_max = 0;
    int cop_max = 0;
    for (auto& p : problems) {
        alp_max = max(alp_max, p[0]);
        cop_max = max(cop_max, p[1]);
    }
    alp = min(alp, alp_max);
    cop = min(cop, cop_max);

    for (int i = 0; i <= alp_max; i++) {
        for (int j = 0; j <= cop_max; j++) {
            dp[i][j] = INF;
        }
    }
    dp[alp][cop] = 0;

    for (int i = alp; i <= alp_max; i++) {
        for (int j = cop; j <= cop_max; j++) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);

            for (auto& p : problems) {
                if (i < p[0] || j < p[1]) continue;

                int ni = min(i + p[2], alp_max);
                int nj = min(j + p[3], cop_max);
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + p[4]);
            }
        }
    }

    return dp[alp_max][cop_max];
}

---

4. 리뷰

효율성 테스트에서 계속 실패했는데 효율 문제가 아니라 코드의 정확성 문제여서 디버깅에 시간이 좀 걸렸다. dp 테이블을 갱신할 때 위치를 잡고 이후 문제들을 적용하며 갱신을 해나가야 모든 경우를 고려한 게 되는데 문제를 먼저 고르고 dp 테이블을 갱신하다 보니 문제 순서에 따라 결과가 달라지는 문제가 생겼었다.

---