백준 11053 가장 긴 증가하는 수열

문제

풀이전략

1. 2차원 배열(cache[start][비교])을 만들어서 자기보다 큰 친구들을 하나씩 다시 재귀를 한다.
2. 다음 재귀로 넘어갈때 1씩 더해주어 증가하는 수열의 길이를 센다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine



int a[1001];
int cache[1001];
int N;

int incSeq(int start){
    if(start > N) return 0;
    int& ret = cache[start];
    if(ret != -1) return ret;
    ret = 1;
    for(int i=start+1; i<=N; i++){
        if(a[start] < a[i]){
            //start에서 갈 수 있는 수열중 제일 긴 길이를 찾는 것이다.
            ret = max(ret, incSeq(i)+1);
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    memset(cache, -1, sizeof(cache));
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }
    int res = 0;
    for(int i=1; i<=N; i++){
        res = max(incSeq(i), res);
    }

    cout << res << endl;

    return 0;
}

소감

자기보다 긴 값이 생길때마다 재귀를 돌려서 다시 그 값을 기준으로 반복하는 아이디어 기억하자.