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

문제 설명

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

문제 풀이

• 다이나믹 프로그래밍을 통해 풀이하였다.
• 사용된 점화식은 다음과 같다.

  dp[알고력][코딩력] = 현재 알고력, 코딩력에서 모든 문제를 다풀기 위해 사용할 최소 코스트

• 위 점화식을 이용하여
  1. 알고력 1 올려주기
  2. 코딩력 1 올려주기
  3. 현재 알고력, 코딩력을 가지고 풀 수 있는 모든 문제에 대해
  -> 문제 풀고 알고력, 코딩력 보상 올려주기
• 주의 사항은 dp 테이블의 사이즈를 Int[max_알고력][max_코딩력]으로 잡을 때 런타임 에러를 발생시키지 않기 위해 예외 처리를 잘 해줘야한다.

소스 코드 (JAVA)

import java.util.Arrays;

class Solution {
    public int[][] probs;
    public int[][] dp;
    public int maxA, maxC, INF = 987654321;

    public int solve(int A, int C) {
        //기저 조건
        if (A >= maxA && C >= maxC) return 0;
        if (dp[A][C] != -1) return dp[A][C];
        int result = INF;
        if (A < maxA) result = Math.min(result, solve(A + 1, C) + 1);
        if (C < maxC) result = Math.min(result, solve(A, C + 1) + 1);
        //가능한 모든 문제 사용
        for (int i = 0; i < probs.length; i++) {
            //불가능 문제 넘김
            if (A < probs[i][0] || C < probs[i][1]) continue;
            //리워드가 0,0인 문제 넘김
            if (probs[i][2] == 0 && probs[i][3] == 0) continue;
            //한쪽 리워드만 무한히 올려주지 않도록 
            if (probs[i][2] == 0 && C + probs[i][3] > maxC) continue;
            if (A + probs[i][2] > maxA && probs[i][3] == 0) continue;
            result = Math.min(result, solve(Math.min(A + probs[i][2], maxA), Math.min(C + probs[i][3], maxC)) + probs[i][4]);
        }

        return dp[A][C] = result;
    }

    public int solution(int alp, int cop, int[][] problems) {
        probs = problems;
        maxA = maxC = 0;
        for (int i = 0; i < problems.length; i++) {
            maxA = Math.max(maxA, problems[i][0]);
            maxC = Math.max(maxC, problems[i][1]);
        }
        dp = new int[maxA + 1][maxC + 1];
        for (int i = 0; i < maxA + 1; i++)
            Arrays.fill(dp[i], -1);
        return solve(Math.min(alp, maxA), Math.min(cop, maxC));
    }
}