[C++] 백준 - 11053 : 가장 긴 증가하는 부분 수열

문제 링크

11053번: 가장 긴 증가하는 부분 수열

 

풀이 ) DP

  길이가 1일 때의 부분 수열의 길이는 1이고,

  2 이상일 때는 앞에서부터 현재 a[1]과 비교하여 a[0]이 더 작다면 memo[0]+1과 memo[1]을 비교하여 더 큰 값을 memo[1]에 넣는다.

  더 큰 수를 예로 들면 길이가 4인 부분 수열에서 a[3]이 a[0], a[1], a[2]와 순차적으로 비교하여 만약 a[0]과 a[2]가 더 작다면 memo[3]은 memo[0]+1과 memo[2]+1 중 더 큰 값을 저장하게 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1001] = {1, };

int main(void)
{
  int n, a[1001] = {0, }, ans = 1;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a+i);

  for(int i = 1; i < n; ++i){
    memo[i] = 1;
    for(int j = 0; j < i; ++j)
      if(a[i] > a[j])
        memo[i] = max(memo[i], memo[j]+1);
  }
  for(int i = 0; i < n; ++i)
    ans = max(ans, memo[i]);
  printf("%d\n", ans);
}

 

주의점 )

  모든 부분 수열의 최소 길이는 1이므로 memo[i] = 1을 매 반복문마다 해준다.