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

문제

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

프로그래머스

모든 문제를 풀 수 있는 알고력과 코딩력을 구하는 데 걸리는 최소 시간을 구하는 문제였다.

 

문제 풀이

DP로 풀었다.

1. cost 1로 알고력 1 올리기
2. cost 1로 코딩력 1 올리기
3. 문제를 풀어 알고력/코딩력 올리기

처음 풀이로는 효율성 테스트 10번이 어떤 수를 써도 시간 초과가 나서(450 * 450 * 6) maxAlp * maxCop * problems 만큼 걸리도록 다시 풀었다.

 

하지만,, 두 번째 풀이도 계속 오류가 났는데, alp와 cop가 최대 alp/cop보다 큰 경우에 0을 리턴하고 끝내게 해서 문제가 없을 줄 알았는데, 둘 중 하나라도 클 경우에 문제가 생기는 것을 알게 됐다. 

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

#define MAX_INT 100000

using namespace std;

int dp[201][201]; //alp, cop

int solution(int alp, int cop, vector<vector<int>> problems) {    
    int maxAlp = 0, maxCop = 0;        
    
    //max 찾기
    for(int i=0;i<problems.size();i++){
        maxAlp = max(maxAlp, problems[i][0]);
        maxCop = max(maxCop, problems[i][1]);        
    }
    
    if(alp >= maxAlp && cop >= maxCop) return 0;
    
    //둘 중 하나라도 큰 경우 위해
    alp = min(alp, maxAlp);
    cop = min(cop, maxCop);
    
    //dp 초기화
    fill(&dp[0][0], &dp[200][200], MAX_INT);          
    dp[alp][cop] = 0;
        
    int changeAlp, changeCop;
    
    for(int i=alp;i<=maxAlp;i++){
        for(int j=cop;j<=maxCop;j++){
            changeAlp = min(i+1, maxAlp);
            changeCop = min(j+1, maxCop);
            dp[changeAlp][j] = min(dp[changeAlp][j], dp[i][j]+1);
            dp[i][changeCop] = min(dp[i][changeCop], dp[i][j]+1);
            
            //problems
            for(vector<int> problem:problems){
                int needAlp = problem[0];
                int needCop = problem[1];
                int plusAlp = problem[2];
                int plusCop = problem[3];
                int cost = problem[4];
                
                if(i<needAlp || j<needCop) continue;
                changeAlp = min(i+plusAlp, maxAlp);
                changeCop = min(j+plusCop, maxCop);
                dp[changeAlp][changeCop] = min(dp[changeAlp][changeCop],dp[i][j]+cost);
            }
            
        }
    }        

    return dp[maxAlp][maxCop];
}

 

처음 풀이 (오답)

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

#define MAX_INT 100000

using namespace std;

int dp[451][451]; //alp, cop

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = MAX_INT;
    int maxAlp = 0, maxCop = 0;        
    
    //max 찾기
    for(int i=0;i<problems.size();i++){
        if(maxAlp < problems[i][0]) maxAlp = problems[i][0];
        if(maxCop < problems[i][1]) maxCop = problems[i][1];
    }
    
    if(alp >= maxAlp && cop >= maxCop) return 0;
    
    //dp 초기화
    fill(&dp[0][0], &dp[450][450], MAX_INT);        
    for(int i=0;i<=alp;i++){
        for(int j=0;j<=cop;j++){
            dp[i][j] = 0;       
        }
    }    
        
    for(int i=alp; i<450;i++){       
        if(i != alp) dp[i][cop] = min(dp[i][cop], dp[i-1][cop] +1);        
        for(int j=cop;j<450;j++){
            if(j!=cop) dp[i][j] = min(dp[i][j], dp[i][j-1] +1);
            //problems
            for(int p=0;p<problems.size();p++){
                int needAlp = problems[p][0];
                int needCop = problems[p][1];
                int plusAlp = problems[p][2];
                int plusCop = problems[p][3];
                int cost = problems[p][4];
                
                if((i-plusAlp) < needAlp || (j-plusCop) < needCop) continue;
                dp[i][j] = min(dp[i][j], dp[i-plusAlp][j-plusCop] + cost);     
            }
            if(i>=maxAlp && j>=maxCop){
                answer = min(answer, dp[i][j]);
            }
        }
    }


    return answer;
}