[프로그래머스]JAVA - Level3. 코딩 테스트 공부

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

프로그래머스

풀이

2022 Kakao tech internship 알고리즘 문제를 1번부터 차근차근 풀어보고있는데 3번부터 어렵다...

이것저것 해보다가 검색해봤더니 동적 계획법 (Dynamic Programming) 을 사용해야하는 문제이다.

 

동적 계획법이란 복잡한 문제를 여러 개의 작은 부분 문제로 나누어서 문제를 해결하는 기법으로 Bottom_Up 과 Top_Down 방법 두 가지가 존재한다. 

 

• Top_Down 방법: 큰 문제에서 작은 부분 문제를 재귀적으로 호출하여 리턴 되는 값을 이용하여 큰 문제를 해결하는 방법
• Bottom_Up 방법: 작은 부분 문제들을 미리 계산해두고 이 부분 문제들을 모아 큰 문제를 해결하는 방법

 

문제에서 알 수 있듯이 우리가 정확하게 알고 있는 건 작은 부분 문제, 즉 알고력과 코딩력이다. 그러므로 Bottom_Up 방법으로 알고리즘 풀이를 진행할 것이다.

 

솔직하게 동적 계획법 정의를 읽었을 때 이해가 되지 않아서 아래처럼 예시 1번의 동적 계획법을 표로 직접 그려봤다. 

 

① 초기 알고력과 코딩력은 (10, 10) 이므로 0을 넣고, 목표치인 (20, 20) 까지 MAX_VALUE 를 넣어준다.

② 선택지는 총 3가지 (알고력 +1, 코딩력 +1, 문제 풀기) 를 했을 때 걸리는 시간을 넣어준다.

 

표를 그려서 해봤을 때 두 번째 문제를 풀 수 있는 조건 (10, 15) 을 달성하기 까지 총 5시간이 소요되기 때문에 (10, 15)에 5를 넣어준다. 이후 문제를 풀었을 때와 알고력, 코딩력을 순수 증가 시켰을 때를 비교하면서 작은 값을 넣어준다.

 

위의 예시에서는 문제를 풀었을 때가 더 적은 시간이 걸리므로 (12, 16) (14, 17) (16, 18) (18, 19) (20, 20) 에 문제를 풀었을 때 소요되는 시간을 더해준다.

 

이 과정을 코드로 변환하면 아래와 같다.

// 알고력 트레이닝
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[i+alp_rwp][j+cop_rwp] = Math.min(dp[i+alp_rwp][j+cop_rwp], dp[i][j] + cost);

 

문제를 풀면서 생기는 변수 2가지

1. 문제를 풀었을 때 목표치를 넘겼을 경우

2. 초기 알고력과 코딩력이 목표치보다 높을 경우

 

for (int m=0; m<problems.length; m++) {
    
    // 현재 알고력과 코딩력이 문제를 해결할 수 있는 조건을 넘었을 경우
    if (i >= problems[m][0] && j >= problems[m][1]) {				
					
        // 알고력과 코딩력이 목표치를 넘겼을 경우
        if (i+problems[m][2] > alp_target && j+problems[m][3] > cop_target) {
            dp[alp_target][cop_target] = Math.min(dp[alp_target][cop_target], dp[i][j] + problems[m][4]);
        } // 알고력이 목표치를 넘겼을 경우 
        else if (i+problems[m][2] > alp_target) {
            dp[alp_target][j+problems[m][3]] = Math.min(dp[alp_target][j+problems[m][3]], dp[i][j]+problems[m][4]);
        } // 코딩력이 목표치를 넘겼을 경우
        else if (j+problems[m][3] > cop_target) {
            dp[i+problems[m][2]][cop_target] = Math.min(dp[i+problems[m][2]][cop_target],dp[i][j]+problems[m][4]);
        } // 목표치에 도달하지 못 한 경우
        else if (i+problems[m][2] <= alp_target && j+problems[m][3] <= cop_target){
            dp[i+problems[m][2]][j+problems[m][3]] = Math.min(dp[i+problems[m][2]][j+problems[m][3]],dp[i][j]+problems[m][4]); 
        }
    }
}

최종적으로 dp 배열에서 [목표알고력][목표코딩력]의 값을 반환하는 방식이기 때문에 문제를 풀었을 때의 값이 목표치를 넘었을 때 [목표알고력][목표코딩력]로 반환해주어야한다.

 

// 초기 알고력, 코딩력 둘 다 목표치보다 높을 경우
if (alp >= alp_target && cop >= cop_target) {
    return;
}

// 초기 알고력이 목표치보다 높을 경우
if (alp >= alp_target) {
    alp = alp_target;
}

// 초기 코딩력이 목표치보다 높을 경우
if (cop >= cop_target) {
    cop = cop_target;
}

문제에 제시되어 있지 않지만 해당 문제를 인식하지않고 풀게 되면 [제출 후 채점하기]에서 수 많은 런타임 에러가 발생한다. 생성한 배열의 크기보다 큰 값을 찾고 있기 때문에 발생하는 에러이기 때문에 초기에 위의 코드를 넣어주면 쉽게 해결할 수 있다.

 

<최종코드>

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int answer = 0;
        int alp_target = 0;
        int cop_target = 0;
        
        for (int i=0; i<problems.length; i++) {
            alp_target = Math.max(problems[i][0], alp_target); // 알고력 최종 목표값
            cop_target = Math.max(problems[i][1], cop_target); // 코딩력 최종 목표값
        }
        
        if (alp >= alp_target && cop >= cop_target) {
            return 0;    
        }
        
        // 처음 설정된 알고력이 최종 목표값보다 높을 경우
        if (alp >= alp_target) {
            alp = alp_target;
        }
        
        // 처음 설정된 코딩력이 최종 목표값보다 높을 경우
        if (cop >= cop_target) {
            cop = cop_target;
        }
        
        int[][] dp = new int[alp_target+2][cop_target+2]; // 최종 목표값 +2 만큼 크기의 dp 배열 생성
        for (int i=alp; i<=alp_target; i++) {
            for (int j=cop; j<=cop_target; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        dp[alp][cop] = 0;
        for (int i=alp; i<=alp_target; i++) {
            for (int j=cop; j<=cop_target; j++) {
            
                // 공부하기
                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);
                
                for (int m=0; m<problems.length; m++) {
					
                    // 현재 알고력과 코딩력이 문제를 해결할 수 있는 조건을 넘었을 경우
                    if (i >= problems[m][0] && j >= problems[m][1]) {
						
                        // 알고력과 코딩력이 목표치를 넘었을 경우
                        if (i+problems[m][2] > alp_target && j+problems[m][3] > cop_target) {
                            dp[alp_target][cop_target] = Math.min(dp[alp_target][cop_target], dp[i][j] + problems[m][4]);
                        } // 알고력이 목표치를 넘겼을 경우
                        else if (i+problems[m][2] > alp_target) {
                            dp[alp_target][j+problems[m][3]] = Math.min(dp[alp_target][j+problems[m][3]], dp[i][j]+problems[m][4]);
                        } // 코딩력이 목표치를 넘겼을 경우
                        else if (j+problems[m][3] > cop_target) {
                            dp[i+problems[m][2]][cop_target] = Math.min(dp[i+problems[m][2]][cop_target],dp[i][j]+problems[m][4]);
                        } // 목표치에 도달하지 못 한 경우
                        else if (i+problems[m][2] <= alp_target && j+problems[m][3] <= cop_target){
                            dp[i+problems[m][2]][j+problems[m][3]] = Math.min(dp[i+problems[m][2]][j+problems[m][3]],dp[i][j]+problems[m][4]); 
                        }
                    }
                }
            }
	    }
        answer = dp[alp_target][cop_target];
        return answer;
    }
}