백준(BOJ) 11053

LIS 문제를 풀었다.

for문은 기존에 풀어봐서 재귀를 이용해 풀었다.

재귀를 사용하려니 더 헷갈렸다.

실수한 점은 lis함수를 재귀를 이용해 구현하면, 필요한 부분만 보게된다는 것이다.

때문에 1 2 3 4 5 1 을 list(5) 로 호출하게되면 1을 리턴하고 끝이 난다.

따라서 lis함수를 메인문에서 N갯수만큼 돌려주어야 한다. 이부분을 놓쳤다.

사실 재귀를 사용하면 필요한 부분만 탐색하기 때문에 for문보다 빠르다는 것은 알고있었다.

하지만 이런 경우, 재귀는 결국 전체를 다 검색해야하기때문에 for문과 같거나 그 이상의 시간복잡도가 걸리게 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int N;
int arr[1000];
int cache[1000];
int lis(int n){
  int& ret = cache[n];
  if(n == 0) return ret = 1;
  if(ret != -1) return ret;
 
  ret = 0;
  int m = 0;
  for(int i = n - 1; i >= 0; i--){
    if(arr[n] > arr[i])
      m = max(lis(i), m);
  }
  return ret = m + 1;
 
}
int main(void){
  scanf("%d", &N);
  for(int i = 0 ; i < N; i++){
    scanf("%d", arr + i);
    cache[i] = -1;
  }
  int result = 1;
  for(int i = N - 1; i >= 0; i--){
      result = max(lis(i), result);
  }
 
  printf("%d\n", result);
 
}