[백준(BOJ)] 11053번: 가장 긴 증가하는 부분 수열 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• DP배열: 각 원소 위치에서 수열 길이의 최댓값 저장
  • DP배열에서 가장 큰 값을 가진 것이 가장 긴 증가하는 수열의 길이 최댓값이다.
• i번째일 때, i번째 전까지의 모든 수(j번째 수)를 탐색하면서 만약 i번째가 j번째 수보다 크다면, 해당 i번째에서 수열 길이의 최댓값을 구해준다.
  • 이전 원소들과 비교 전 DP[i] = 1로 초기화한다.
  • DP[i] = max(DP[i], DP[j] + 1)로 구하는데, DP[j] + 1과 비교하는 이유는 이전 원소 j번째에서 구한 수열 길이의 최댓값을 i번째 원소 위치에서인 1과 더했을 때가 최댓값일 수 있기 때문이다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>
using namespace std;

int main(){
    int N, result=0;
    scanf("%d", &N);
    int A[N]={};
    int DP[N] = {};

    for(int i=0; i<N; i++){
        scanf("%d", &A[i]);
    }

    for(int i=0; i<N; i++){
        DP[i] = 1;
        for(int j=0; j<i; j++){
            if(A[i]>A[j]){
                DP[i] = max(DP[i], DP[j]+1);
            }
        }
        result=max(result, DP[i]);
    }
    printf("%d", result);
}

 

 

👏 결과

---