[2022 KAKAO TECH INTERNSHIP] 코딩 테스트 공부

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118668

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 dp를 이용하여 문제를 풀 수 있습니다. 완전 탐색으로 문제를 접근하게 될 경우 모든 경우의 수를 변경해가며 결과를 체크해야하기 때문에 시간 초과가 발생합니다. 따라서 dp를 이용하여 최솟값을 저장하는 방식으로 문제를 풀어야 합니다.

1. dp[i][j] = 알고력 i, 코딩력 j까지 도달하는데 최단 시간 으로 dp 배열을 설정합니다.
2. 문제를 풀지 않고 학습할 경우 각각
   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);
   으로 dp배열을 채웁니다.
3. 문제를 풀었을 때의 경우 기존값과 풀었을 때의 값의 최솟값을 계산합니다.
   dp[new_alp][new_cop] = Math.min(dp[new_alp][new_cop], dp[i][j]+cost);

다음은 코드입니다.

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        //  현재 문제들 중 알고력과 코딩력의 최댓값 저장
        int alm=0,com=0;
        for(int i=0;i<problems.length;i++){
            if(alm < problems[i][0]) alm = problems[i][0];
            if(com < problems[i][1]) com = problems[i][1];
        }
        
        // dp[i][j] = 알고력 i, 코딩력 j까지 도달하는데 최단 시간
        int[][] dp = new int[alm+1][com+1];
        
        // alp와 alm 중 최솟값부터 dp 배열 채우기 시작
        alp = Math.min(alp,alm);
        cop = Math.min(cop,com);
        
        // 초기값 dp[alp][cop] = 0;
        for(int i=0;i<alm+1;i++) Arrays.fill(dp[i],Integer.MAX_VALUE);
        dp[alp][cop] = 0;
        
        // dp[Math.min(alp,alm)][Math.min(cop,com)] 부터 dp[alm][com]까지 dp 배열 최신화
        for(int i=alp;i<=alm;i++){
            for(int j=cop;j<=com;j++){
                // 문제 풀지 않고 학습할 경우
                // 이 때 i,j가 위의 최댓값을 넘으면 안됨 (최댓값이 구하는 값이기 때문에)
                if(i<alm) dp[i+1][j] = Math.min(dp[i+1][j],dp[i][j]+1);
                if(j<com) dp[i][j+1] = Math.min(dp[i][j+1],dp[i][j]+1);
                
                // i와 j가 각각 alp_req, cop_req보다 크거나 같을 경우 문제 풀기 처리
                for(int k=0;k<problems.length;k++){
                    int alp_req = problems[k][0];
                    int cop_req = problems[k][1];
                    int alp_rwd = problems[k][2];
                    int cop_rwd = problems[k][3];
                    int cost = problems[k][4];
                    
                    if(i>=alp_req && j>=cop_req){
                        // new_alp,new_cop가 위의 최댓값을 넘으면 안됨 (최댓값이 구하는 값이기 때문에)
                        int new_alp = Math.min(i+alp_rwd, alm);
                        int new_cop = Math.min(j+cop_rwd, com);
                        
                        // 문제 풀었을 때 걸리는 비용과 현재값과의 최솟값 비교
                        dp[new_alp][new_cop] = Math.min(dp[new_alp][new_cop], dp[i][j]+cost);
                    }
                }
            }
        }
        
        return dp[alm][com];
    }
}