징검다리

풀이

배열 내에서 연속으로 증가하는 개수의 최댓값을 구하는 문제였다. 먼저 dp 배열 내 모든 원소에 1을 저장시켜준 후 2중 for문을 통해 dp를 진행시켰다. 사용된 점화식은 다음과 같다.

dp[i] = max(dp[i],dp[j]+1)

i보다 작은 인덱스들에 한해서 현재 i레벨에서 저장된 값보다 작은 값이 있으면, 이전 레벨에서의 dp값에 1을 더하며 최댓값을 구하였다.

 

#include<iostream>
#include<vector>
using namespace std;
int N,dp[3001];
int main(int argc, char** argv)
{
  int ans=0;
  cin>>N;
  fill(dp,dp+N,1);
  vector<int> v(N);
  for(int i=0;i<N;i++){
    cin>>v[i];
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<i;j++){
      if(v[j]<v[i]){
        dp[i] = max(dp[i],dp[j]+1);
      }
    }
  }
  for(int i=0;i<N;i++){
    ans = max(ans,dp[i]);
  }
  cout<<ans;
  return 0;
}