코딩 테스트 공부

문제

프로그래머스

현재 자신의 알고력과 코딩력으로 주어진 문제를 풀 수 있는 최소 시간을 구하는 문제이다.

모든 문제는 최소 알고력과 코딩력이 주어지고 자신의 현재 알고력과 코딩력이 모두 문제의 알고력과 코딩력을 넘어야 문제를 풀 수 있다.

문제를 풀면 알고력과 코딩력이 문제에 따라 증가된다. 물론 드는 시간도 제각각이다.

한 문제를 여러번 풀 수 있다.

또 다르게 알고력과 코딩력을 늘릴 수 있는 방법은 1의 시간을 들이며 알고력, 코딩력 둘중 하나를 늘릴 수 있다.

 

초기 알고력(alp), 코딩력(cop)가 주어집니다. 또한 문제 리스트가 주어진다. 

문제 리스트의 구성요소는 다음과 같다.(필요 알고력, 필요 코딩력, 얻게 되는 알고력, 얻게 되는 코딩력, 드는 시간)

 

예를 들어 초기 값이 다음과 주어지면 총 15의 시간을 들이면 problems의 모든 문제를 풀 수 있다.

 

주어진 여러 조건에 따라 최소값을 구해야 하기 때문에 dp 문제이다.

먼저 점화식은 다음과 같다.

dp[i][j]  = i의 알고력과, j의 코딩력을 달성하는 데 최소시간

 

알고력, 코딩력을 상승시키는 방법은 총 3가지가 존재한다.

 

1) 알고력 상승 (단순 1시간 소비)

dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)

 

2) 코딩력 상승 (단순 1시간 소비)

dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)

 

3) 문제 해결

dp[i +문제 해결해서 얻는 알고력][j + 문제 해결해서 얻는 코딩력]

= min(dp[i +문제 해결해서 얻는 알고력][j + 문제 해결해서 얻는 코딩력], dp[i][j] + 문제 푸는데 드는 시간)

 

이렇게 dp를 진행했을 경우 아래와 같은 2차원 배열로 진행된다.

초기 알고력, 코딩력의 드는 시간은 0이다.

 

여기서 고려해야할 사항이 있다.

1) 만약 초기 알고력과 코딩력이 모든 문제의 알고력 과 코딩력 보다 크거나 같으면 드는 시간은 그냥 0이다.

2) 우리는 최종 알고력과 코딩력을 풀 수 있는 시간만 찾으면 되기 때문에 초기 알고력과 초기 코딩력 중 주어진 문제 보다 크면 

최종 값으로 초기화 해줘야 한다.

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;

 

 

이제 dp 배열을 모두 처음에 MAX값으로 초기화 해주고 현재 알고력과 코딩력에 대해서만 0으로 설정해준다.

int [][]dp = new int[alp_target+2][cop_target+2];
        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;

 

이제 본격적으로 dp를 시작해준다.

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 : problems){
                    //현재 알고력과 코딩력이 문제를 해결할 수 있는 경우
                    if(i >= m[0] && j >= m[1]){
                        
                        //알고력과 코딩력이 목표치를 넘겼을 경우
                        if(i+m[2] >alp_target && j+m[3]>cop_target)
                            dp[alp_target][cop_target]=Math.min(dp[alp_target][cop_target], dp[i][j] + m[4]);
                        //알고력이 목표치를 넘겼을 경우
                        else if(i+m[2] > alp_target)
                            dp[alp_target][j+m[3]] = Math.min(dp[alp_target][j+m[3]], dp[i][j] +m[4]);
                        //코딩력이 목표치를 넘겼을 경우
                        else if(j+m[3] > cop_target)
                            dp[i+m[2]][cop_target] = Math.min(dp[i+m[2]][cop_target], dp[i][j] +m[4]);
                        //아직 알고력, 코딩력 모두 목표치를 못 넘겼을 경우
                        else if(i+m[2] <= alp_target && j +m[3] <=cop_target)
                            dp[i+m[2]][j+m[3]] = Math.min(dp[i+m[2]][j+m[3]], dp[i][j]+m[4]);
                        
                    }
                }
            }
        }
        
        answer = dp[alp_target][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];
        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 : problems){
                    //현재 알고력과 코딩력이 문제를 해결할 수 있는 경우
                    if(i >= m[0] && j >= m[1]){
                        
                        if(i+m[2] >alp_target&&j+m[3]>cop_target)
                            dp[alp_target][cop_target]=Math.min(dp[alp_target][cop_target], dp[i][j] + m[4]);
                        else if(i+m[2]>alp_target)
                            dp[alp_target][j+m[3]] = Math.min(dp[alp_target][j+m[3]], dp[i][j] +m[4]);
                        else if(j+m[3]>cop_target)
                            dp[i+m[2]][cop_target] = Math.min(dp[i+m[2]][cop_target], dp[i][j] +m[4]);
                        else if(i+m[2]<=alp_target && j +m[3] <=cop_target)
                            dp[i+m[2]][j+m[3]] = Math.min(dp[i+m[2]][j+m[3]], dp[i][j]+m[4]);
                        
                    }
                }
            }
        }
        
        answer = dp[alp_target][cop_target];
        
        return answer;
    }
}