[알고리즘] 2022 KAKAO TECH INTERNSHIP 코딩테스트 공부 (Java)

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

프로그래머스

 

이 문제는 정확성과 효율성을 모두 고려해야하는 문제였다.

 

알고력과 코딩력을 기준치만큼 최소한의 시간 안에 도달해야하는 문제였고,

 

문제를 풀고 나서는 최단거리 형태로도 풀 수 있지 않을까 생각이 들긴 했지만,

 

우선은 전형적인 dp 문제라는 생각이 들어, dp 배열을 선언하여 문제를 해결했다.

 

dp[i][j]는 알고력 i와 코딩력 j를 도달하기 위한 최단 시간을 나타내는 배열이고,

 

dp 배열의 크기는 모든 문제 중에 알고력과 코딩력 각각 최대 요구치를 alpMax, copMax라 했을 때

 

dp[alpMax+1][copMax+1] 만큼을 할당하여 사용했다.

 

이후 초기값을 넉넉하게 설정해두고 현재 alp와 cop부터 alpMax와 copMax까지 반복문을 돌면서

 

1시간씩 공부를 해서 능력을 1씩 올리는 경우와, 문제들 중 풀 수 있는 문제를 풀어 능력을 올리는 경우를 확인하여

 

dp값에 매번 최소 값을 갱신해주었다.

 

이 때 문제를 풀어 알고력 혹은 코딩력이 alpMax와 copMax를 넘어가는 경우가 발생하면 dp 배열의 크기를 벗어나게 되므로

 

넘어가는 경우에는 달성하면 되는 최대치인 alpMax나 copMax에서 그 값을 갱신하게끔 구현했다.

 

 

import java.util.*;
import java.math.*;
class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int alpMax,copMax;
        int dp[][];
        
        alpMax = alp;
        copMax = cop;
        
        for(int prob[] : problems){
            alpMax = Integer.max(alpMax,prob[0]);
            copMax = Integer.max(copMax,prob[1]);
        }
        
        dp = new int[alpMax+1][copMax+1];
        
        for(int i=0;i<=alpMax;i++){
            for(int j=0;j<=copMax;j++){
                dp[i][j] = 1000000;
            }
        }
        
        dp[alp][cop]=0;
        
        for(int i=alp;i<=alpMax;i++){
            for(int j=cop;j<=copMax;j++){
                
                if(i+1<=alpMax){
                    dp[i+1][j] = Integer.min(dp[i][j]+1, dp[i+1][j]);
                }
                
                if(j+1<=copMax){
                    dp[i][j+1] = Integer.min(dp[i][j]+1, dp[i][j+1]);                    
                }

                for(int prob[] : problems){
                    if(i >= prob[0] && j >= prob[1]){
                        int curAlp = Integer.min(alpMax, i+prob[2]);
                        int curCop = Integer.min(copMax, j+prob[3]);
                        
                        dp[curAlp][curCop] = Integer.min(dp[curAlp][curCop], dp[i][j]+prob[4]);
                    }
                }
            }
        }
        
        return dp[alpMax][copMax];
    }
}