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

leehyunjon·2022년 9월 4일

카카오 프로그래머스

Algorithm

목록 보기

107/162

코딩 테스트 공부 : https://school.programmers.co.kr/learn/courses/30/lessons/118668

Problem

Solve

완탐으로 풀어보려고 했으나 코딩력이 부족해서 다른 분의 풀이를 보았다.

DP를 이용해 Bottom Up으로 문제를 풀어가는 방식으로 풀이가 가능했다.

초기 알고력과 코딩력을 가지고 모든 문제를 풀기위한 알고력과 코딩력을 가지는데 걸리는 최소 시간을 구하는 문제이다.
즉, 모든 문제에서 가장 높은 알고력과 코딩력을 목표 알고력, 코딩력으로 설정하고 초기 알고력과 코딩력을 목표까지 도달하는데 걸리는 시간을 DP로 구한다.

접근 방법

특정 알고력과 코딩력까지 걸리는 시간을 구하기 위해서는 알고력과 코딩력을 1의 시간으로 1씩 증가 시키는 방법과 문제를 풀어서 특정 시간을 할당해 특정 알고력과 코딩력을 얻는 방법이 있다.
dp[i+1][j] = Math.min(dp[i][j]+1, dp[i+1][j]) //알고력 +1과 +1의 시간
dp[i][j+1] = Math.min(dp[i][j]+1, dp[i][j+1]) //코딩력 +1과 +1의 시간
dp[i+alp_rwd][j+cop_rwd] = Math.min(dp[i][j]+cost, dp[i+alp_rwd][j+cop_rwd]) //알고력 +alp_rwd, 코딩력 +cop_rwd와 +cost의 시간
으로 특정 알고력과 코딩력을 얻는데 걸리는 시간을 dp에 갱신할 수 있다.

그리고 알고력과 코딩력은 목표로 정한 값에 도달하면 되기 때문에 목표로 정한 값을 초과해서 가질 필요는 없다.
그렇기 때문에 i+alp_rwd나 j+cop_rwd가 목표 값을 초과했을 경우 목표값으로 변경해서 걸리는 시간을 갱신해준다.

예를 들어 목표 알고력이 10, 코딩력이 10이고 현재 알고력이 5, 코딩력이 7일때, 어떤 문제를 풀면 alp_rwd = 5, cop_rwd = 5를 얻고 cost = 10을 받게 된다면 알고력은 10, 코딩력은 12가 된다.
하지만 우리는 초과된 코딩력은 그 이후에 필요하지 않다. 그러므로 12인 코딩력을 10으로 갱신해서 dp에 +10된 시간을 해당 값과 비교하여 작은 값으로 갱신해주게되는 것이다.

주의할 점

초기 알고력, 코딩력이 목표 값보다 작게 주어질 경우 결과는 0의 시간을 가지게 된다.
그러므로 위의 경우에는

if(alp > goalAlp){
	alp = goalAlp;
}
if(cop > goalCop){
	cop = goalCop;
}

목표 값으로 갱신해주게 된다면 목표까지 걸리는 시간이 0이 되게 된다.

이렇게 하면 모든 경우의 알고력과 코딩력을 돌기 때문에 목표 알고력 * 목표 코딩력의 반복이 필요하고 각 알고력과 코딩력에서 문제수 만큼의 반복이 발생하기 떄문에 O(목표 알고력 * 목표 코딩력 * 문제 수)의 시간복잡도가 발생한다.

Code

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
    	//목표 알고력과 코딩력
        int goalAlp = 0;
		int goalCop = 0;
        //목표 값 구하기
		for (int[] p : problems) {
			goalAlp = Math.max(goalAlp, p[0]);
			goalCop = Math.max(goalCop, p[1]);
		}

		//초기 값이 목표값보다 크다면 목표값으로 갱신한다.
		if (alp > goalAlp)
			alp = goalAlp;
		if (cop > goalCop)
			cop = goalCop;

		//dp에서 목표 알고력과 코딩력의 값을 구해야하기 때문에 +1
        //코드 구현상 goalAlp과 goalCop에서도 시간을 +1씩 필요로 하는 과정이 포함되기 때문에 +1을 해주어 총 +2만큼의 dp를 초기화 해준다.
		int[][] dp = new int[goalAlp + 2][goalCop + 2];
        //해당 알고력과 코딩력의 최소 시간의 값을 가져야하기 때문에 최대값으로 초기화
		for (int a = alp; a <= goalAlp; a++) {
			for (int c = cop; c <= goalCop; c++) {
				dp[a][c] = Integer.MAX_VALUE;
			}
		}

		//초기 알고력과 코딩력부터 시작하기 때문에 0의 시간으로 설정해준다.
        //초기 값이 목표값보다 큰 경우 0으로 반환되는 이유
		dp[alp][cop] = 0;

		//초기 알고력, 코딩력부터 목표 알고력 코딩력까지 각 +1씩의 공부 또는 문제를 풀어서 특정 알고력과 코딩력을 얻는데 걸리는 시간을 dp에 갱신한다.
		for (int a = alp; a <= goalAlp; a++) {
			for (int c = cop; c <= goalCop; c++) {

				//알고력 +1의 작업
				dp[a + 1][c] = Math.min(dp[a][c] + 1, dp[a + 1][c]);
                //코딩력 +1의 작업
				dp[a][c + 1] = Math.min(dp[a][c] + 1, dp[a][c + 1]);

				//해당 알고력, 코딩력에서 문제를 풀어 얻는 알고력과 코딩력 계산
				for (int[] p : problems) {
					int alpReq = p[0];
					int copReq = p[1];
					int alpRwd = p[2];
					int copRwd = p[3];
					int cost = p[4];

					//현재 alp, cop로 해당 문제를 풀 수 있을 때
					if (a >= alpReq && c >= copReq) {
						//문제를 풀었는데 alp, cop가 goalAlp, goalCop를 오버했을때.
						if (a + alpRwd > goalAlp && c + copRwd > goalCop) {
							//목표 알고력, 코딩력에 시간을 갱신해준다.
							dp[goalAlp][goalCop] = Math.min(dp[a][c] + cost, dp[goalAlp][goalCop]);
						}
						//alp이 목표 알고력을 넘어갔을때
						else if (a + alpRwd > goalAlp) {
							//넘어간 알고력을 목표 알고력으로 갱신해준다.
							dp[goalAlp][c + copRwd] = Math.min(dp[a][c] + cost, dp[goalAlp][c + copRwd]);
						}
						//cop이 목표 코딩력을 넘어갔을때
						else if (c + copRwd > goalCop) {
							//넘어간 코딩력을 목표 코딩력으로 갱신해준다.
							dp[a + alpRwd][goalCop] = Math.min(dp[a][c] + cost, dp[a + alpRwd][goalCop]);
						} else if (a + alpRwd <= goalAlp && c + copRwd <= goalCop) {
							dp[a + alpRwd][c + copRwd] = Math.min(dp[a][c] + cost, dp[a + alpRwd][c + copRwd]);
						}
					}
				}
			}
		}

		return dp[goalAlp][goalCop];
    }
}