문제

Programmers Lv3, 코딩 테스트 공부

핵심

• 모든 문제를 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구해야 한다. 알고리즘 공부를 해서 시간당 1의 알고력을 높일 수 있고, 코딩 공부를 해서 시간당 1의 코딩력을 높일 수 있다. 또한, 문제를 풀어 x 시간을 투자하여 a, b의 알고력과 코딩력을 높일 수 있다. 모든 문제를 풀 수 있는 알고력과 코딩력을 만드는 최소 시간을 구한다.

1. dfs

• 알고리즘 공부를 하거나, 코딩 공부를 하거나, 문제를 푸는 모든 경우를 구해 최솟값을 갱신하는 방법인 dfs로 접근하였다.

dfs(alp + 1, cop, cnt + 1, maxAlp, maxCop, problems, isVisited);

dfs(alp, cop + 1, cnt + 1, maxAlp, maxCop, problems, isVisited);

for (var p : problems) {
	if (alp >= p[0] && cop >= p[1]) {
		dfs(alp + p[2], cop + p[3], cnt + p[4], maxAlp, maxCop, problems, isVisited);
	}
}

• 위에 처럼 간단히 수식을 구할 수 있으나, 최솟값을 갱신하는 로직에 대해선 고민이 필요하다. 가장 어려운 문제의 알고력과 코딩력에 도달하기 위한 최소 시간을 X라고 하자. 만약 알고력과 코딩력을 제한하지 않는다면, 둘 중 부족한 하나를 채우기 위해 알고력 또는 코딩력이 가장 어려운 문제의 알고력과 코딩력보다 커질 수 있다. 가장 어려운 문제의 알고력을 초과하더라도 최소 시간이 될 수 있으므로 초과했다면, 비교를 위해 최고 알고력을 기준으로 제한하는 로직이 필요하다.

dfs 깊이 초과 에러( at Solution.dfs(Unknown Source) ...)

if (alp > maxAlp) alp = maxAlp;

if (cop > maxCop) cop = maxCop;

isVisited[alp][cop] = Math.min(isVisited[alp][cop], cnt);

if (alp == maxAlp && cop == maxCop) return;

• 단순히 위처럼 최댓값에 도달했을 경우에만 종료 조건을 잡으면, 수많은 경우의 수로 인해 에러가 발생한다. 답이 될 가능성이 없는 것들은 제외하여 경우의 수를 줄일 필요가 있다. (가지치기)

• 방문하지 않은 곳은 최댓값으로 초기화한다. 방문했다면 해당 알고력, 코딩력에 도달하기까지 걸린 시간을 갱신한다. 또 방문했다면, 시간이 단축되는 경우가 아니면 탐색을 종료한다. 이는 재귀가 수없이 깊어지고 많아지는 것을 방지한다.

if (isVisited[alp][cop] <= cnt) return;
        
isVisited[alp][cop] = Math.min(isVisited[alp][cop], cnt);

1) 코드

import java.util.*;

class Solution {

    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = -1;
        int maxCop = -1;
        for (var p : problems) {
            maxAlp = Math.max(maxAlp, p[0]);
            maxCop = Math.max(maxCop, p[1]);
        }

        int[][] isVisited = new int[151][151];
        for (var row : isVisited) Arrays.fill(row, Integer.MAX_VALUE);

        dfs(alp, cop, 0, maxAlp, maxCop, problems, isVisited);

        return isVisited[maxAlp][maxCop];
    }

    void dfs(int alp, int cop, int cnt, int maxAlp, int maxCop, int[][] problems, int[][] isVisited) {
        if (alp > maxAlp) alp = maxAlp;
        
        if (cop > maxCop) cop = maxCop;

        if (isVisited[alp][cop] <= cnt) return;
        
        isVisited[alp][cop] = Math.min(isVisited[alp][cop], cnt);

        if (alp == maxAlp && cop == maxCop) return;
        
        dfs(alp + 1, cop, cnt + 1, maxAlp, maxCop, problems, isVisited);
        
        dfs(alp, cop + 1, cnt + 1, maxAlp, maxCop, problems, isVisited);
        
        for (var p : problems) {
            if (alp >= p[0] && cop >= p[1]) {
                dfs(alp + p[2], cop + p[3], cnt + p[4], maxAlp, maxCop, problems, isVisited);
            }
        }
    }
}

2) 시간복잡도

• $n = (maxAlp - alp) + (maxCop - cop)$
• $O(problems.length+2)^n$
  

2. dp

• dfs 풀이와 비슷하게 알고리즘 공부를 하거나, 코딩 공부를 하거나, 문제를 푸는 모든 경우를 구한다. $n = (maxAlp - alp) + (maxCop - cop)$ 개의 상태를 가지며 각 상태에서 가능한 경우는 3가지고, 이 3가지 중 매번 최솟값을 저장한다.
• 정확한 DP값을 구하기 위해 시작 값은 현재 문제에서 필요로 하는 최대치와 현재 지닌 능력 중 작은 값을 기준으로 한다. 이유는 가장 어려운 문제를 기준으로 배열을 만들었는데, 현재 지닌 능력이 더 크다면 outofIndex가 발생하기 때문이다.

1) 코드

import java.util.*;

class Solution {

    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = -1;
        int maxCop = -1;
        for (var p : problems) {
            maxAlp = Math.max(maxAlp, p[0]);
            maxCop = Math.max(maxCop, p[1]);
        }

        int[][] dp = new int[maxAlp + 1][maxCop + 1];
        for (var row : dp) Arrays.fill(row, Integer.MAX_VALUE);

        alp = Math.min(alp, maxAlp);
        cop = Math.min(cop, maxCop);

        dp[alp][cop] = 0;

        for (int i = alp; i <= maxAlp; i++) {
            for (int j = cop; j <= maxCop; j++) {
                if (i < maxAlp) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                }
                if (j < maxCop) {
                    dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
                }

                for (var p : problems) {
                    if (i >= p[0] && j >= p[1]) {
                        int newAlp = Math.min(i + p[2], maxAlp);
                        int newCop = Math.min(j + p[3], maxCop);
                        dp[newAlp][newCop] = Math.min(dp[newAlp][newCop], dp[i][j] + p[4]);
                    }
                }
            }
        }

        return dp[maxAlp][maxCop];
    }
}

2) 시간복잡도

• $n = (maxAlp - alp) + (maxCop - cop)$
• $O((problems.length+2) * n)$