[프로그래머스][C++] 코딩 테스트 공부 (249)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

사실 맨 처음 문제를 읽고 생각이 난 풀이는, 다익스트라를 활용한 최소거리를 찾는 풀이였다.

다만 다익스트라를 적용시키려면 그레프를 먼저 만들어야 하는데, 이부분이 만만치 않다 생각되었다.

 

두번째로 든 생각은 DP를 이용한 풀이 방식이다.

잘 생각해보면, 예를 들어 알고력 20, 코딩력 20에 도달하기 위해서는 알고력 i (i<20), 코딩력 j (j < 20) 을 필수적으로 거쳐가야 한다.

이는 당연한게 알고력이나, 코딩력이 떨어지지는 않기 떄문이다.

 

따라서 더 큰 값을 구하기 위해, 그 안에 더작은 값부터 구해야 한다.

 

• 알고리즘을 공부하여 알고력을 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)
• 문제 하나를 선택하여 알고력과 코딩력을 높이는 경우:
  dp[i+alp_rwd][j+cop_rwd] = min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost) (단, i >= alp_req이고 j >= cop_req)

 

처음에 이렇게만 풀면 될줄 알았다. 물론 초기 테스트 2개 또한 성공적으로 통과한다.

 

문제는 다음과 같은 예외가 존재한다는 점 이다.

 

EX) 목표 코딩 20 , 목표 알고 20,   현재 알고력 18 , 현재  코딩력17 일때,

 

문제 1번을 풀었을때 얻는 알고력이 3, 코딩력이 3 이라면, 1번을 풀었을때 자신의 스탯은 알고력 21, 코딩력 20이다.

우리의 목표는 둘다 20, 20이 되기를 원한다.

 

결과적으로 dp[목표알고치][목표코딩치]를 반환해야하는데,  위에있는 케이스를 놓친다.

 

그렇다면 우리가 해줘야할것은 알고력이 목표알고력을 넘엇을때, 교정작업 (알고력 21 = 목표알고력 20) 을 해야한다.

if(i+alp_rwd > max_alp && j+cop_rwd > max_cop) {
    DP[max_alp][max_cop] = min(DP[max_alp][max_cop], DP[i][j] + cost);
} else if (i+alp_rwd > max_alp) {
    DP[max_alp][j+cop_rwd] = min(DP[max_alp][j+cop_rwd], DP[i][j] + cost);
} else if (j+cop_rwd > max_cop) {
    DP[i+alp_rwd][max_cop] = min(DP[i+alp_rwd][max_cop], DP[i][j] + cost);
} else {
    DP[i+alp_rwd][j+cop_rwd] = min(DP[i+alp_rwd][j+cop_rwd], DP[i][j] + cost);   
}

위와 같이 max값들을 넘었을때 교정작업을 해주면 된다!

 

나의 코드

#include <bits/stdc++.h>

#define INF 2147000000
using namespace std;

int max_alp = -1, max_cop = -1;
int DP[200][200];

int solution(int alp, int cop, vector<vector<int>> problems) {
    
    for (auto e : problems) {
        max_alp = max(max_alp, e[0]);
        max_cop = max(max_cop, e[1]);
    }
    
    if(max_alp <= alp && max_cop <= cop){
        return 0;
    }
        
    if(alp >= max_alp){
        alp = max_alp;
    }
    
    if(cop >= max_cop){
        cop = max_cop;
    }
    
    for(int i = 0; i < 200; i++) {
        for(int j = 0; j < 200; j++) {
            DP[i][j] = INF;
        }
    }
    
    DP[alp][cop] = 0;
    for(int i = alp; i <= max_alp; i++) {
        for(int j = cop; j <= max_cop; j++) {
            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);
            
            for(auto e : problems) {
                int alp_req = e[0];
                int cop_req = e[1];
                int alp_rwd = e[2];
                int cop_rwd = e[3];
                int cost = e[4];
                
                if(i >= alp_req && j >= cop_req) {
                    if(i+alp_rwd > max_alp && j+cop_rwd > max_cop) {
                        DP[max_alp][max_cop] = min(DP[max_alp][max_cop], DP[i][j] + cost);
                    } else if (i+alp_rwd > max_alp) {
                        DP[max_alp][j+cop_rwd] = min(DP[max_alp][j+cop_rwd], DP[i][j] + cost);
                    } else if (j+cop_rwd > max_cop) {
                        DP[i+alp_rwd][max_cop] = min(DP[i+alp_rwd][max_cop], DP[i][j] + cost);
                    } else {
                        DP[i+alp_rwd][j+cop_rwd] = min(DP[i+alp_rwd][j+cop_rwd], DP[i][j] + cost);   
                    }
                }
            }
        }
    }
    
    return DP[max_alp][max_cop];
}