코딩테스트 공부

문제

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

문제 해결 아이디어

알고력과 코딩력을 달성하기 위한 최소 시간을 dp[i][j]로 구성하는게 포인트🎯

1. 목표 알고력, 코딩력 설정

   • problems에서 모든 alp_req 중 최댓값과 cop_req 중 최댓값

2. DP 배열 구성

   • dp[i][j]를 알고력 i와 코딩력 j를 달성하기 위한 최소 시간을 저장하는 2차원 배열로 정의
   • 초기 상태 dp[alp][cop] = 0으로 시작하며, 나머지 값은 큰 값(Integer.MAX_VLAUE)으로 초기화
   • 단, 초기 alp 또는 cop가 목표치를 넘는다면 목표치로 맞춤 (배열 길이 고려)

3. 상태 전이

   • 공부(알고리즘/코딩)
     • 알고리즘 공부: dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
     • 코딩 공부: dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
   • 문제 풀이
     • 만약 현재 상태 (i, j)가 문제 p의 요구치(alp_req, cop_req)를 만족한다면, 문제 p를 풀어 새 상태 (min(target_alp, i + alp_rwd), min(target_cop, j + cop_rwd))로 전이되고, 소요 시간 cost가 추가

4. 최종 답안

   • 목표 알고력과 코딩력을 달성한 상태 dp[target_alp][target_cop]의 값이 최소 총 공부 시간이 됩니다.

코드

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        // 1. 목표 알고력, 코딩력 설정 (각 문제의 최대 요구치)
        int maxAlp = 0, maxCop = 0;
        for (int[] prob : problems) {
            maxAlp = Math.max(maxAlp, prob[0]);
            maxCop = Math.max(maxCop, prob[1]);
        }
        // 초기치가 목표치를 초과하면 목표치로 맞춤
        alp = Math.min(alp, maxAlp);
        cop = Math.min(cop, maxCop);
        
        // 2. dp 배열 초기화
        int[][] dp = new int[maxAlp + 1][maxCop + 1];
        for (int i = 0; i <= maxAlp; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[alp][cop] = 0;
        
        // 3. DP 전이 (알고리즘 공부, 코딩 공부, 문제 풀기)
        for (int i = alp; i <= maxAlp; i++) {
            for (int j = cop; j <= maxCop; j++) {
                if (dp[i][j] == Integer.MAX_VALUE) continue;
                
                // 3-1. 알고리즘 공부: 알고력 1 증가
                if (i < maxAlp) {
                    dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);
                }
                // 3-2. 코딩 공부: 코딩력 1 증가
                if (j < maxCop) {
                    dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j] + 1);
                }
                // 3-3. 각 문제 풀이
                for (int[] prob : problems) {
                    if (i >= prob[0] && j >= prob[1]) {
                        int newAlp = Math.min(maxAlp, i + prob[2]);
                        int newCop = Math.min(maxCop, j + prob[3]);
                        dp[newAlp][newCop] = Math.min(dp[newAlp][newCop], dp[i][j] + prob[4]);
                    }
                }
            }
        }
        return dp[maxAlp][maxCop];
    }
}