[프로그래머스/자바] 코딩 테스트 공부 풀이 - 2020 KAKAO TECH INTERNSHIP

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

프로그래머스

 

 

2020 KAKAO TECH INTERNSHIP

Level 3 문제다.

 

 

맨 처음의 알고력과 코딩력을 알고 있기 때문에

bottom-up dp를 통해 구현했다.

레벨 3치고는 꽤나 단순하게 접근 가능한 문제인 것 같다.

 

2차원 배열을 통해 알고력과 코딩력에 도달하기 위해 필요한 시간을 저장한다.

예를 들어 dp[10][20]에 2가 저장되어 있다면

알고력 10, 코딩력 20에 도달하기까지 2초의 시간이 필요한 것이다.

 

풀어야 할 문제에서 요구하는 알고력과 코딩력 중 가장 큰 값을 찾아

그 배열값을 구하면 된다.

 

 

 

이 때 주의해야 할 점 두 가지가 있다.

 

1) 문제를 풀어 알고력과 코딩력을 늘린다고 할 때, 현재 그 문제를 풀 능력이 되는지 체크

2) 구해야 할 최대 알고력과 코딩력을 넘을 경우를 무시한다면 최소 시간을 정확히 찾을 수 없음

 

2)의 예시로

구해야 할 배열의 값이 dp[30][30]이고

10, 10, 20, 20, 1

10 10, 10, 10, 5

라는 두 문제를 풀 수 있을 때,

 

dp[20][20]에서 첫번째 문제를 풀면 dp[20][20] + 1이지만

두 번째 문제를 두번 풀면 dp[20][20] + 10이 되어 최소 시간을 찾을 수 없다.

즉 문제를 푼 후의 능력이 구해야 할 최대 알고력과 코딩력을 넘는 경우에도 dp[30][30]에 시간을 대입해야 한다.

 

 

처음엔 2)를 생각해내지 못해 시간이 조금 걸렸다.

여러 케이스를 빠르게 생각해내는 것이 중요한 것 같다.

 

class Solution {
    static int[][] dp;
	static int maxAlp, maxCop;
    
    public int solution(int alp, int cop, int[][] problems) {
		maxAlp = alp;
        maxCop = cop;
        
        for(int i=0;i<problems.length;i++) {
			if(maxAlp < problems[i][0])
				maxAlp = problems[i][0];
			if(maxCop < problems[i][1])
				maxCop = problems[i][1];
		}

		dp = new int[maxAlp + 1][maxCop + 1];
		for(int i=alp;i<=maxAlp;i++)
			for(int j=cop;j<=maxCop;j++)
				dp[i][j] = Integer.MAX_VALUE;

		dp[alp][cop] = 0;
		dp(alp, cop, problems);

		return dp[maxAlp][maxCop];
	}

	static void dp(int alp, int cop, int[][] problems) {
		for(int i=alp;i<=maxAlp;i++) {
			for(int j=cop;j<=maxCop;j++) {
				// 알고리즘 공부
				if(i + 1 <= maxAlp)
					dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);

				// 코딩 공부
				if(j + 1 <= maxCop)
					dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);

				// 문제 풀기
				for(int k=0;k<problems.length;k++) {
					if(problems[k][0] <= i && problems[k][1] <= j) { // 풀 수 있는 문제라면
						int increaseAlp = problems[k][2];
						int increaseCop = problems[k][3];
						int hour = problems[k][4];
						
						// 최대 범위를 넘은 경우 최대범위로 조정
						if(i + increaseAlp > maxAlp) 
							increaseAlp = maxAlp - i;
						if(j + increaseCop > maxCop)
							increaseCop = maxCop - j;

						dp[i + increaseAlp][j + increaseCop] = Math.min(dp[i + increaseAlp][j + increaseCop], dp[i][j] + hour);
					}
				}
			}
		}
	}
}