Memo
•
기본적으로 루프를 0 부터 N - 1까지 돌면서 확인합니다.
•
cal_max함수는 첫 번째 인자로 함수 밖에서 비교중인 인덱스, 두 번째 인자로 함수 밖에서 비교중인 인덱스에 들어있는 값을 받습니다.
•
cal_max 함수 내에서 첫 번째 인덱스 보다 큰 값들을 비교합니다.
•
비교하는 과정에서 첫 번째 인자의 위치에 있는 값보다 크다면 함수를 재귀적으로 호출하여 그 인덱스에 들어있는 dp값을 바꿔줍니다.
•
다음 루프에서 해당 인덱스에 dp값이 들어있다면 그것을 그대로 사용합니다.
Code
제출 날짜
@3/23/2021
메모리
2016 KB
시간
0 ms
#include <iostream>
#include <vector>
#include <algorithm>
size_t N;
std::vector<int> arr;
std::vector<int> dp;
int ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N;
arr.resize(N);
dp.resize(N);
for (size_t i = 0 ; i < N ; i++)
std::cin >> arr[i];
}
int cal_max(int p_i, int val)
{
int max_val = 0;
if (p_i >= static_cast<int>(N))
return (0);
if (dp[p_i])
return (dp[p_i]);
for (size_t i = p_i + 1 ; i < N ; i++)
if (arr[p_i] < arr[i])
max_val = std::max(max_val, cal_max(i, arr[i]));
dp[p_i] = max_val + val;
return (max_val + val);
}
void solve()
{
for (size_t i = 0 ; i < N ; i++)
ans = std::max(ans, cal_max(i, arr[i]));
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
