[C++] 11053번 가장 긴 증가하는 부분 수열 - DP

#include <iostream>

#define MAX_N 1001

using namespace std;

int Max[MAX_N];  //가장 긴 부분 수열의 길이 (메모리제이션)
int map[MAX_N];  //수열
int N;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i=1; i<=N; i++)
        cin >> map[i];
    
    for(int i=1; i<=N; i++) {
        Max[i]=1;
        for(int j=1; j<i; j++) {  //자신보다 작고 증가하는 부분 수열이 더 길면 바꿈
            if(map[j]<map[i] && Max[i]<Max[j]+1)
                Max[i] = Max[j]+1;
        }
    }
    
    int max=0;
    for(int i=1; i<=N; i++) {  //제일 긴 부분 수열을 출력
        if(max<Max[i])
            max=Max[i];
    }
    cout << max;
    
    return 0;
}

 

쉽다. 골드 이전까지의 DP문제는 모두 그냥 반복문으로 풀면 되는 것 같다.

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다