프로그래머스 | 코딩 테스트 공부 - java

프로그래머스

 

# 핵심

DP

 

 

맨 처음에 DFS로 풀려고 했는데 정확성은 맞았으나 효율성에 대해서 한문제도 통과를 못한다는 빛나는 성과를 보였기에 다른 접근방법을 찾아야만 했다...

 

솔직히 혼자서는 못풀었고 문제 해설을 적극 참고한 덕분에 겨우 풀 수 있었다.. 

(참고: https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/ )

 

어떻게든 기존 아이디어로 풀어보려고 시도하다보니 코드가 난잡해지고 덕지덕지 조건문만 붙는데다가 결국 또 못풀었다

한참 안풀릴 때에는 그냥 과감하게 새로운 아이디어를 생각하는 것이 그냥 더 낫겠다는 걸 많이 느꼈다..

 

왜 최단 시간을 구하는데 DP 고려를 안해봤을까.. 아직 난 DP 문제가 너무 어려운 것 같다.

최단시간 구할때는 대표적으로 DP!!!!! 꼭 고려해보자!!!!!!!!!!!!!!!!!!! (BFS도 같이)

 

 

 

카카오의 벽은 역시나 높구나 하는걸 절실히 느낀 하루였다. 

열심히 하는 것 말고는 답이 없다

 

-나중에 다시 풀면서 해설 달기-

 

 

# 통과 코드

import java.util.*;

class Solution {

    static final int INF = 1_000_000; // 대충 큰 값
    int maxAlp; // 문제 중 가장 높은 알고력 수치
    int maxCop; // 문제 중 가장 높은 코딩력 수치

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

        // dp[alp][cop] = (alp,cop) 위치까지 도달하는데 걸리는 최단 시간
        int[][] dp = new int[maxAlp + 1][maxCop + 1];

        alp = Math.min(alp, maxAlp); // alp가 이미 maxAlp보다 더 클 수 있음 -> 오버플로우 발생 방지
        cop = Math.min(cop, maxCop); // cop도 동일

        for (int[] ints : dp) {
            Arrays.fill(ints, INF);
        }

        dp[alp][cop] = 0; // 시작 위치

        for(int i = alp; i <= maxAlp; i++) {
            for(int j = cop; j <= maxCop; j++) {
                // 기본 문제 풀 경우
                if(i + 1 <= maxAlp) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                }
                if(j + 1 <= maxCop) {
                    dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
                }
                // 선택 문제 풀 경우
                for (int[] problem : problems) {
                    if(problem[0] <= i && problem[1] <= j) { // 풀 수 있는 경우
                        int nextAlp = Math.min(maxAlp, i + problem[2]); // maxAlp 범위를 초과하는 경우 
                        int nextCop = Math.min(maxCop, j + problem[3]); // maxCop 범위를 초과하는 경우 
                        dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[i][j] + problem[4]);
                    }
                }
            }
        }
        return dp[maxAlp][maxCop];
    }
}