[프로그래머스 카카오 2022기출문제] 코딩 테스트 공부

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

프로그래머스

처음 접근 방식:

1. 반복문을 돌며 최대 필요한 alp,cop를 구한다 => alpMax, copMax

2. alp,cop가 시작점이 된다.

3. 반복문을 돌며 i,j에서 문제를 풀면 도달할 수 있는 위치에 비용을 기록한다. (각각 공부하는 +1 에도 기록한다)

    이 때, 배열을 충분히 크게 만들어, 목표치에 초과할 경우도 기록할 수 있게 한다. 

4. alpMax,copMax보다 큰 배열의 범위를 돌며, cost의 최소치를 탐색한다.

 

결과 : 런타임에러 및 오답, 효율성체크 : 오답.

 

수정한 접근 방식:

1. 반복문을 돌며 최대 필요한 alp,cop를 구한다 => alpMax, copMax

2. 런타임에러 방지를위해 alp와 alpMax, cop와 copMax를 Max값 취해준다.

    input에따라서 탐색을 못할때가 있음 ex) alp가 alpMax보다 클 때

3. 반복문을 돌며 i,j에서 문제를 풀면 도달할 수 있는 위치에 비용을 기록한다. (각각 공부하는 +1 에도 기록한다)

    이때, 필요한 수치를 초과하는 경우, 필요한 cop,alp가 해당하는 배열의 위치에 max를 돌려 넣어준다. (추후 한번 더 검사를 할필요 없음 수정 전 코드의 4번)

4. dp[alpMax][copMax]의 값을 출력한다.

 

3,4번을 수정하며, 메모리와 시간을 절약할 수 있다.

import java.util.*;
class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int alpMax = 0;
        int copMax = 0;
        for (int[] ints : problems) {
            alpMax = Math.max(ints[0], alpMax);
            copMax = Math.max(ints[1], copMax);
        }
        alpMax = Math.max(alpMax,alp);
        copMax = Math.max(copMax,cop);
        if(alp>=alpMax&&cop>=copMax) return 0;
        int[][] dp = new int[alpMax + 1][copMax +1];
        for (int i = 0; i < alpMax+1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE-10000);
        }
        dp[alp][cop] = 0;
        for (int i = alp; i <= alpMax; i++) {
            for (int j = cop; j <= copMax; j++) {
                if (i < alpMax) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                }
                if (j < copMax) {
                    dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
                }
                for (int[] problem : problems) {
                    if (i >= problem[0] && j >= problem[1]) {
                        int next_alp = Math.min(alpMax, i + problem[2]);
                        int next_cop = Math.min(copMax, j + problem[3]);
                        dp[next_alp][next_cop] = Math.min(dp[next_alp][next_cop], dp[i][j] + problem[4]);
                    }
                }
            }

        }
        return dp[alpMax][copMax];
    }
}