[C++, 코딩테스트] Softeer : 징검다리 with DP(기억하기 풀이법)

일단 이 문제는 문제조차 이해하기 힘들었다. 문제 자체가 좀 설명을 좀 애매하게 해놔서 다른 사람들의 문제 해석을 보고 나서야 이해가 되었다.

 

일단 이 문제를 풀기 전에 DP 알고리즘에 대해서 알아보자.

먼저 DP는 dynymic programming 의 약자로 이 이름만으로는 어떤 알고리즘인지 예측하기 쉽지 않다. 그래서 나는 이 알고리즘을 이제 기억하기 풀이법이라고 부를 것이고 그렇게 기억할 것이다. 

 

기억하기 풀이법은 이전에 계산 했던 내용을 기억하는 방식으로 DFS, BFS로 풀 수 있지만 그 계산양이 너무 많을 경우 사용하는 것이 좋다. 계속 풀이법이라고 말을 했는데 DP는 알고리즘이 아닌 기법의 한 종류이다. 개발자마다 구현방식이 다 다를 것이고 풀이법도 많다고 한다.

 

 

#include<iostream>
#include<vector>

using namespace std;



int main(int argc, char** argv)
{
    int N;
    int num;
    vector<int> arr;
    vector<int> dp;
    cin >> N;
    
    for (int i = 0; i < N; i++){
        cin >> num;
        arr.push_back(num);
    }
    dp.resize(N, 1);
    
    for (int i = 0; i < N; i++){
        // 9 * 10^6 <= 1억
        int find = 0;
        for (int j = 0; j < i; j++){
            if (arr[i] > arr[j]){
                find = max(find, dp[j]);
            }
        }
        dp[i] = find + 1;
    }

    int answer = 1;
    for (int i = 0; i < N; i++){
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;
    return 0;
}

 

기억

1. resize

배열의 사이즈를 줄이고 늘릴 수 있다. 

 

 

풀이

arr : [3, 2, 1 4, 5]

dp : [1, 1, 1, 2, 3]

 

dp 배열에 계산한 값들을 기록해놔서 다음 요소의 최대값을 계산할 때 앞에 높이가 낮은 애들 중에서 dp 값이 가장 높은 값에 +1을 한 값을 저장하면 된다.

 

 

풀이쓰다가.. 날라가서 대충 썼다.. ㅜ

 

참고