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

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

프로그래머스

풀이

최단 시간으로 전체 문제를 해결할 수 있는 알고력과 코딩력을 얻는 문제이다.

이때, 최종 상태(알고력, 코딩력)는 항상 이전 상태(임의의 알고력, 코딩력을 얻는데 걸렸던 최단 시간)에서 최단 시간을 통해 최종 알고력과 코딩력을 얻는데 걸리는 시간이다. 

따라서 부분문제의 해답이 전체 문제의 해답이 되므로 DP를 사용할 수 있다.

DFS 방식으로 모든 경우의 수를 탐색하여 정확성을 얻고, 메모이제이션을 사용해 효율성 또한 달성할 수 있다.

이때, alp와 cop값을 문제에서 주어진 조건으로 제

1. solve(alp, cop, problems) 함수는 alp, cop 상태에서 최종 상태까지 도달하는데 걸리는 시간을 리턴한다.

2. 뻗어나갈 수 있는 상태는 문제를 풀거나, 알고력 또는 코딩력을 증가시키는 것이다.

문제 풀기: res = min(res, solve(alp+reward, cop+reward)+cost)

알고력 증가: res = min(res, solve(alp+1, cop)+1)

3. 참조형 변수 res를 사용해 현재 alp, cop 상태에서 최종 상태에 도달하는데 걸리는 최솟값을 업데이트 한다.

4. 문제를 풀거나 알고력 또는 코딩력을 증가시키는 상황에서, 알고력 또는 코딩력 증가분 중 한쪽이 0일 때 무한루프를 방지하기 위해, 최종 max값에 도달한 후에는 자동으로 dp에 저장된 값을 리턴하므로 무한루프를 방지할 수 있다.

5. 또한, dp에는 최솟값이 저장되므로 현재 상태에서 답을 아는 경우 바로 리턴 하면 된다.

 

리뷰

시간제한이 10초여서 완전탐색을 해야겠구나 생각은 했는데 오랜만이여서 그런지 재귀+dp는 생각하지 못했다. 결국 다른 분의 코드를 참고했지만 좋은 공부가 되었던 문제이다.. 처음엔 우선순위큐(다익스트라)를 사용해서 해결해보려 했는데 다시 시도해봐야겠다.

#include <string>
#include <vector>

using namespace std;
int maxAlp, maxCop;
int dp[151][151];

int solve(int alp, int cop, const vector<vector<int>>& problems){
    // 모든 문제 해결 가능 조건
    if (alp>=maxAlp && cop>=maxCop) return 0;
    
    // 메모리 최대 공간 제한
    if (alp > maxAlp) alp=maxAlp;
    if (cop > maxCop) cop=maxCop;
    // 구해야 하는 값  res
    // alp가 계속증가하고 cop가 고정 된 상태 종료 조건
    // 최소 값으로 이미 업데이트가 끝낫기 때문에 리턴
    int& res = dp[alp][cop];
    if (res!=0) return res;
    
    res = 1e9;
    // 문제 해결 (현재 상태에서 가능한 모든 경우 탐색)
    for (auto& i:problems){
        if (alp<i[0] || cop<i[1]) continue;
        res = min(res, solve(alp+i[2], cop+i[3], problems)+i[4]);
    }
    // 공부
    res = min(res, solve(alp+1, cop, problems)+1);
    res = min(res, solve(alp, cop+1, problems)+1);
    
    return res;
}

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    for (auto i:problems){
        maxAlp=max(maxAlp, i[0]);
        maxCop=max(maxCop, i[1]);
    }
    
    answer = solve(alp, cop, problems);
    
    return answer;
}