99클럽 코테 스터디 42일차 TIL / [프로그래머스] 코딩 테스트 공부

오늘의 학습 키워드

---

DP

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 코딩 테스트 공부
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        Algorithm[] algorithms = new Algorithm[problems.length + 2];

        algorithms[0] = new Algorithm(0, 0, 1, 0, 1); // 알고리즘 공부
        algorithms[1] = new Algorithm(0, 0, 0, 1, 1); // 코딩 공부

        int idx = 2;
        int maxAlpReq = Integer.MIN_VALUE;
        int maxCopReq = Integer.MIN_VALUE;

        for(int[] problem : problems) {
            algorithms[idx++] = new Algorithm(problem[0], problem[1], problem[2], problem[3], problem[4]);
            maxAlpReq = Math.max(maxAlpReq, problem[0]);
            maxCopReq = Math.max(maxCopReq, problem[1]);
        }
        
        if(alp >= maxAlpReq && cop >= maxCopReq) return 0;
        
        alp = Math.min(alp, maxAlpReq);
        cop = Math.min(cop, maxCopReq);

        // row: alp, col: cop, value: time
        int[][] mem = new int[maxAlpReq + 1][maxCopReq + 1];
        for(int i=alp;i<=maxAlpReq; i++){
            for(int j=cop;j<=maxCopReq; j++){
                mem[i][j] = Integer.MAX_VALUE;
            }
        }

        mem[alp][cop] = 0;
        
        for (int curAlp = alp; curAlp <= maxAlpReq; curAlp++) {
            for (int curCop = cop; curCop <= maxCopReq; curCop++) {
                for (Algorithm algorithm : algorithms) {
                    if (curAlp < algorithm.alp_req || curCop < algorithm.cop_req) continue;
                    
                    int afterAlp = curAlp + algorithm.alp_rwd;
                    int afterCop = curCop + algorithm.cop_rwd;
                    
                    afterAlp = Math.min(afterAlp, maxAlpReq);
                    afterCop = Math.min(afterCop, maxCopReq);
                    
                    mem[afterAlp][afterCop] = Math.min(mem[afterAlp][afterCop], mem[curAlp][curCop] + algorithm.cost);
                }
            }
        }

        return mem[maxAlpReq][maxCopReq];
    }

    static class Algorithm {
        int alp_req;
        int cop_req;
        int alp_rwd;
        int cop_rwd;
        int cost;

        public Algorithm(int alp_req, int cop_req, int alp_rwd, int cop_rwd, int cost) {
            this.alp_req = alp_req;
            this.cop_req = cop_req;
            this.alp_rwd = alp_rwd;
            this.cop_rwd = cop_rwd;
            this.cost = cost;
        }
    }
}

접근

• DP를 활용하여 문제를 풀이했고, DP 배열은 mem[row][col] = value의 형태입니다.
  • row: 알고력
  • col: 코딩력
  • value: 해당 알고력과 코딩력을 갖기 위해 필요한 시간
• 본격적인 DP 로직을 수행하기 전, 데이터 처리 수행 내용입니다.
  • problem 입력 배열의 정보는 5개로, 인덱스로 접근했을 때 가독성이 떨어진다고 판단하여 데이터 저장만을 위한 Algorithm 클래스를 만들었습니다.

    	static class Algorithm {
        int alp_req;
        int cop_req;
        int alp_rwd;
        int cop_rwd;
        int cost;
    
        public Algorithm(int alp_req, int cop_req, int alp_rwd, int cop_rwd, int cost) {
            this.alp_req = alp_req;
            this.cop_req = cop_req;
            this.alp_rwd = alp_rwd;
            this.cop_rwd = cop_rwd;
            this.cost = cost;
        }
    }

  • 알고력과 코딩력을 향상시킬 수 있는 방법에는 문제를 푸는 것 말고 공부를 하는 방식도 존재합니다. 이후 문제를 순회하며 DP 배열을 채워갈 것인데, 굳이 문제와 공부 케이스를 나누지 않고 코드를 단순화하고자 Algorithm 배열에 문제와, 공부 모두 저장하여 관리했습니다.

    Algorithm[] algorithms = new Algorithm[problems.length + 2];
    
    algorithms[0] = new Algorithm(0, 0, 1, 0, 1); // 알고리즘 공부
    algorithms[1] = new Algorithm(0, 0, 0, 1, 1); // 코딩 공부
    
    int idx = 2;
    int maxAlpReq = Integer.MIN_VALUE;
    int maxCopReq = Integer.MIN_VALUE;
    
    for(int[] problem : problems) {
        algorithms[idx++] = new Algorithm(problem[0], problem[1], problem[2], problem[3], problem[4]);
        maxAlpReq = Math.max(maxAlpReq, problem[0]);
        maxCopReq = Math.max(maxCopReq, problem[1]);
    }

    • 이렇게 problem들을 algorithms 배열에 옮기는 과정에서, 문제에서 요구되는 최대 알고력/코딩력을 구하여 maxAlpReq, maxCopReq 변수에 저장합니다.
  • 이후 DP 배열의 처음부터 순회하면서 채워갈 것인데, 여기서 처음이란? → alp, cop 입니다. (여기까진 소요 시간: 0이므로)
    • 그런데, 최초에 주어진 alp, cop 값이 요구되는 alp, cop 값보다 클 수 있습니다.
      • 만약, 이미 모든 문제를 풀 수 있는 경우에는 바로 리턴하여 작업을 종료합니다.

        if(alp >= maxAlpReq && cop >= maxCopReq) return 0;

      • 요구되는 alp, cop 값보다 큰 경우가 존재할 수 있으니, 더 작은 값으로 시작 값을 갱신합니다.

        alp = Math.min(alp, maxAlpReq);
        cop = Math.min(cop, maxCopReq);

• 최초에 DP 배열은 최댓값으로 초기화를 해줍니다. (alp, cop 지점은 0으로 초기화)

  // row: alp, col: cop, value: time
  int[][] mem = new int[maxAlpReq + 1][maxCopReq + 1];
  for(int i=alp;i<=maxAlpReq; i++){
      for(int j=cop;j<=maxCopReq; j++){
          mem[i][j] = Integer.MAX_VALUE;
      }
  }
  
  mem[alp][cop] = 0;

• 이제 DP 배열의 시작 지점부터 for문을 돌면서 배열을 채워갑니다.

  for (int curAlp = alp; curAlp <= maxAlpReq; curAlp++) {
      for (int curCop = cop; curCop <= maxCopReq; curCop++) {
          for (Algorithm algorithm : algorithms) {
              if (curAlp < algorithm.alp_req || curCop < algorithm.cop_req) continue;
              
              int afterAlp = curAlp + algorithm.alp_rwd;
              int afterCop = curCop + algorithm.cop_rwd;
              
              afterAlp = Math.min(afterAlp, maxAlpReq);
              afterCop = Math.min(afterCop, maxCopReq);
              
              mem[afterAlp][afterCop] = Math.min(mem[afterAlp][afterCop], mem[curAlp][curCop] + algorithm.cost);
          }
      }
  }

  • 만약, 현재 지점에서 문제를 풀이할 수 없는 경우에는 continue
  • 풀이할 수 있는 경우에는 Math.min(해당 지점에서의 시간, 현재 지점에서 문제를 풀이했을 때의 시간)으로 값을 갱신합니다.
  • 최대 요구 값보다 큰 지점이 정답이 되는 경우도 존재할 수 있습니다. 하기의 코드가 그 역할을 수행합니다. (이 코드가 없다면, 배열 범위를 초과하여 에러 발생)

    afterAlp = Math.min(afterAlp, maxAlpReq);
    afterCop = Math.min(afterCop, maxCopReq);

소요 시간

2시간