[Java/C++] 프로그래머스 Level 3 - 코딩테스트 연습

문제 링크

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

[2022 KAKAO TECH INTERNSHIP]에 나왔던 문제

현재 프로그래머스에서 정답률은 20%로 Level 3 중에서도 낮은데,
실제 시험에서는 훨씬 더 낮지 않았을까?

다른 사람이 푼걸 보니, 꽤나 풀이법이 다양하게 나오는 문제였다.
그리고 최적화를 아주 깐깐하게 보는 문제였다.

 

 

---

문제 핵심 및 풀이

---

행동의 선택지 생각하기

어떻게 보면 문제를 그냥 정리하는 것일 수도 있는데,
난 여기서 큰 힌트를 얻었다.

점수는 알고력과 코딩력이라는 2가지의 유형이 존재하므로,
이를 각각 A, B라고 두겠다. 

초기 점수가 (A, B)라고 생각해 보자.
최단 시간을 얻기 위해 할 수 있는 행동은 무엇이 있을까?

1. 알고리즘 공부 → (A+1, B) = 1
2. 코딩 공부 →(A, B+1) = 1
3. 문제 풀기(조건부) → ( A + alp_rwd , B + cop_rwd ) = cost

크게는 이 3가지이다.
물론 마지막 방법은 A와 B가 특정 점수를 만족해야 풀 수 있다.

이를 (A, B)의 관점에서 생각해서
"어떻게 A와 B 점수를 만드는가?"를 생각해도 좋다.

이런 식으로 생각해 보자.

(A, B) 일 때의 최단시간을 구하기 위해선 어떻게 해야 할까?
일단 A, B가 될 수 있는 후보들을 생각해 보자.

1. 알고리즘 공부 →(A-1, B) + 1
2. 코딩 공부 →(A, B-1) + 1
3. 문제 풀기(조건부)→( A - alp_rwd , B - cop_rwd ) + cost

이런 식으로 나올 텐데,
위 3개 중에서 가장 작은 것이 최단시간이 된다.

결국엔 또
(A-1, B)의 최단 시간,
(A, B-1)의 최단시간
 ( A - alp_rwd , B - cop_rwd )의 최단 시간을
또 알아야 한다.

결론적으로 이 문제는 재귀적인 특성을 가진다는 것이다.

특정한 계산을 반복하는 것을 막기 위해
메모라이징 기법을 이용하는 DP 문제이다.

bottom-up 방식을 사용할지, top-down 방식을 사용할지는 선택이다.
필자는 bottom-up으로 해당 문제를 풀었다.

 

---

최대 배열의 크기(어디까지 계산해줘야 하나)

쉽게 생각해 보면, problems을 모두 순회하여
제일 높은 알고력(maxAlp)과 코딩력(maxCop)을 알아내기만 하면 된다.

그래서 (A, B) 쌍 값이 이 둘보다 모두 같거나 높아지면
모든 문제를 풀 수 있다는 것이다,

여기서 애매한 부분은
maxAlp와 maxCop를 초과하더라도,
최단시간일 수 있다는 것이다.

나는 부분을 그냥 maxAlp보다 높은 값이 나오면
무조건 maxAlp로 바꿔주는 방식으로 해결했다.

그러면 (maxAlp, maxCop)에서의 최솟값이 답이 될 것이기 때문이다.

자세한 것은 코드에서 확인하면 편할 것이다.
주석을 통해 달아 두겠다.

 

 

---

실수하기 쉬운 부분

특정 테스트 케이스에서 계속 시간초과가 날 수 있다.
이는 입력으로 maxAlp와 maxCop보다 높은 alp, cop가 들어올 때 가 있기 때문이다.

그래서 이를 따로 처리해줘야 한다.
나도 이 부분 때문에 시간을 많이 잡아먹었다.

 

 

---

코드 구현

---

C++ 구현 코드

↓

#include <string>
#include <vector>
#include <algorithm>

#define MAX 99999999
using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    // 문제를 푸는데 필요한 점수는 150이 최대이기 
    // 때문에 alp,cop도 150까지만 쓰면 됨
    
    // dp[a][b] = k : 알고력 a, 코딩력 b를 만들기 위한 최단 시간은 k
    int dp[152][152];
    
    
    int maxAlp = alp;
    int maxCop = cop;
    
    
    fill(&dp[0][0],&dp[151][152],MAX); // 모든 값 가장 높게 초기화
    dp[alp][cop] = 0; // 시작하는 값은 당연히 0초로 초기화
    
    // 순회하여 각각의 max값을 찾아줌
    for(auto problem : problems){
        maxAlp = max(maxAlp,problem[0]);
        maxCop = max(maxCop,problem[1]);
    }
    
    // 기존의 alp와 cop가 가장 높은 값이라면 계산 필요없음
    if(maxAlp == alp && maxCop == cop) return 0;
    
    // 초기값부터 시작하여 max값까지만 해주면됨
    // 왜냐하면 어차피 그 이상 값은 모두 maxAlp로 바꿔줄 것
    for(int i = alp; i <= maxAlp; i++){
        for(int j = cop; j <= maxCop; j++){
            // 알고리즘 + 1 
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1);
            // 코딩 + 1
            dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1);
            
            // 문제 순회
            for(auto problem : problems){
                // 조건 만족시
                if(i >= problem[0] && j >= problem[1]){
                    // 기존 점수와 문제에서 얻은 점수의 합이 maxAlp를 넘지 못하게함
                    int nextA = min(maxAlp,problem[2]+i);
                    int nextC = min(maxCop,problem[3]+j);
                    // 해당 문제를 풀었을 때의 점수와 비교
                    dp[nextA][nextC] = min(dp[nextA][nextC],dp[i][j]+problem[4]);
                }
            }
        }
    }
    return dp[maxAlp][maxCop]; // 정답값
}

 

 

 

 

---

Java 구현 코드

↓

 

import java.util.*;

class Solution {
    static final int MAX = 999999999; // min에서 안걸리도록
    
    // 문제를 푸는데 필요한 점수는 150이 최대이기 
    // 때문에 alp,cop도 150까지만 쓰면 됨
    int[][] dp = new int[152][152];

    
    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = alp;
        int maxCop = cop;
        
        for(int[] problem : problems){
            maxAlp = Math.max(maxAlp,problem[0]);
            maxCop = Math.max(maxCop,problem[1]);
        }
        // 기존의 alp와 cop가 가장 높은 값이면 계산 필요없음
        if(maxAlp == alp && maxCop == cop) return 0;
        
        // 모든 값 가장 높게 초기화
        for(int i = 0; i <= maxAlp; i++)
            for(int j = 0; j <= maxCop; j++) dp[i][j] = MAX;
        
        
        dp[alp][cop] = 0; // 초기값은 당연히 최단시간 0
        
        
        // 초기값부터 시작하여 max값까지만 해주면됨
    	// 왜냐하면 어차피 그 이상 값은 모두 maxAlp로 바꿔줄 것
        for(int i = alp; i <= maxAlp; i++){
            for(int j = cop; j <= maxCop; j++){
            	// 알고리즘 + 1
                dp[i+1][j] = Math.min(dp[i+1][j],dp[i][j]+1);
                
                // 코딩 + 1
                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]){
                    	// 기존 점수와 문제에서 얻은 점수의 합이 max를 넘지 못하게함
                        int nextA = Math.min(maxAlp,i + problem[2]);
                        int nextC = Math.min(maxCop,j + problem[3]);
                        // 해당 문제를 풀었을 때의 점수와 비교
                        dp[nextA][nextC] = Math.min(dp[nextA][nextC],dp[i][j]+problem[4]);
                    }
                }
            }
        }
        
        return dp[maxAlp][maxCop];
    }
}

 

 

---

시행착오

처음에는 Top-down으로 풀었다가, 망했다.
그래서 bottom-up으로 푸니까 좀 풀리더라.

근데 처음에는 저렇게 안 풀고 다르게 풀었는데,
이상하게 배열을 500씩 잡으니까 되더라.

근데 그건 테스트 케이스로 500 이상의 값을 넣지 않아서 그런 거였다.

사실은 틀리는 코드여서 그냥 올리기엔 꺼림칙해서
이리 저래 알아보고 수정한 걸 블로그에 올렸다.

카카오 코테 어렵다 너무.

https://toss.me/howudong

howudong님에게 보내주세요