99클럽 코테 스터디 42일차 TIL + 코딩 테스트 공부(DP)

 

 

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 코딩 테스트 공부 (문제 링크)
• 동적 계획법(DP)

 

 

---

 

 

 

문제 설명

당신은 코딩 테스트를 준비하기 위해 알고리즘과 코딩 구현 능력을 높여야 합니다. 각각의 문제를 풀기 위해 필요한 알고력과 코딩력이 주어지고, 이를 높이기 위한 다양한 방법(알고리즘 공부, 코딩 공부, 문제 풀이)이 제공됩니다. 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 데 걸리는 최단시간을 구하는 문제입니다.

제한사항

• 초기 알고력과 코딩력은 0 ≤ alp, cop ≤ 150 범위 내의 정수로 주어집니다.
• 문제 정보는 [alp_req, cop_req, alp_rwd, cop_rwd, cost] 형태의 배열로 주어지며, 이 배열의 길이는 1 ≤ 100 이하입니다.
• 문제를 풀거나 공부를 통해 알고력과 코딩력을 증가시킬 수 있습니다.

입출력 예

alp = 10, cop = 10
problems = [[10,15,2,1,2],[20,20,3,3,4]]
result = 15

alp = 0, cop = 0
problems = [[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]]
result = 13

예시 설명

• 첫 번째 예시에서는 15의 시간이 소요되어 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.
• 두 번째 예시에서는 13의 시간이 소요되어 모든 문제를 풀 수 있는 능력을 얻을 수 있습니다.

 

 

---

 

 

문제 접근

1. 문제 이해
   • 현재 알고력과 코딩력을 기준으로 문제를 풀거나 공부를 통해 능력을 키워나가야 합니다.
   • 목표는 주어진 모든 문제를 풀 수 있을 정도로 알고력과 코딩력을 높이는 데 필요한 최소 시간을 구하는 것입니다.
2. 풀이 방법
   • 동적 계획법(DP)을 사용하여 현재 상태에서 가능한 모든 문제 풀이 또는 공부 방법을 탐색하고, 최소 시간을 계산합니다.
   • 각 상태에서 다음 상태로 이동하는 데 걸리는 시간을 계산하고, 이를 DP 배열에 저장하며 최적 경로를 찾아갑니다.

 

 

풀이 - Java 코드

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = 0, maxCop = 0;

        // 문제들 중 가장 높은 알고력과 코딩력을 구함
        for (int[] problem : problems) {
            maxAlp = Math.max(maxAlp, problem[0]);
            maxCop = Math.max(maxCop, problem[1]);
        }

        alp = Math.min(alp, maxAlp);
        cop = Math.min(cop, maxCop);

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

        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[] problem : problems) {
                    if (i >= problem[0] && j >= problem[1]) {
                        int nextAlp = Math.min(maxAlp, i + problem[2]);
                        int nextCop = Math.min(maxCop, j + problem[3]);
                        dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[i][j] + problem[4]);
                    }
                }
            }
        }

        return dp[maxAlp][maxCop];
    }
}

풀이 설명

1. 초기화
   • 먼저, 주어진 문제들 중에서 필요한 최대 알고력과 코딩력을 계산합니다.
   • 주어진 초기 알고력과 코딩력의 값을 최대값에 맞게 조정합니다.
   • dp 배열을 큰 값으로 초기화하며, dp[alp][cop]을 0으로 설정합니다.
2. DP 계산
   • dp 배열을 순차적으로 순회하며, 알고력 또는 코딩력을 1씩 증가시키거나, 문제를 풀어서 능력을 증가시키는 경우의 시간을 갱신합니다.
   • 각 상태에서 가능한 모든 다음 상태로의 이동을 고려하며 최소 시간을 저장합니다.
3. 결과 반환
   • 목표인 maxAlp와 maxCop에 도달하는 데 필요한 최소 시간을 dp[maxAlp][maxCop]에서 가져옵니다.

 

 

---

 

 

마무리하며

이번 문제는 동적 계획법(DP)을 활용해 최단 경로를 계산하는 문제였습니다.

여러 가지 상태에서의 최적 경로를 찾기 위해 DP 배열을 사용하여 해결할 수 있었습니다.