[👊DP뿌시기 #7] (BOJ 11053) 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

접근법

6
10 20 10 30 20 50

위 예시를 이용해보자.

예를 들어 30을 포함하는 가장 긴 증가 부분 수열이 무엇일까?

 

30 이전까지의 배열 중 가장 긴 증가 부분 수열을 가진 값에 자신을 더하기만 하면 된다.

과정을 정리하면 다음과 같다.

 

1. 원하는 인덱스 (i) 이전까지의 인덱스(j) 중 값이 작은 값을 선택한다.

2. j에 해당하는 값들 중 DP가 가장 큰 값에 자신을 포함한 값을 DP[i]에 저장한다.

 

이제 30을 기준으로 차근차근 정리해보자.

 

DP[i]를 i번째 인덱스를 포함하는 가장 긴 증가 부분 수열로 정의하자.

 

처음에 DP[3]을 1로 초기화한다.

왜냐하면 자신만 포함하는 것이 기본이기 때문

 

이제 0부터 2(j)까지 중 ARR[j]가 ARR[3]보다 작은 값을 선택한다.

증가하는 부분 수열이기 때문이다.

 

 10과 30을 포함하는 부분 수열의 크기(DP[0] + 1 = 2)은 기존 30의 크기(DP[3] = 1) 보다 크므로,  DP[3]에 2를 저장한다.

 

20의 경우, DP[1]+1 > DP[3] 이므로 DP[3] = DP[1]+1

 

2번 인덱스의 경우 DP[2]+1 < DP[3] 이므로

기존 DP[3]의 값을 그대로 가져간다.

 

이와 같은 방식으로 5번 인덱스까지 진행해주면, O(N^2)의 시간복잡도를 가지고 문제를 해결할 수 있다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;

int dp[10001];
int arr[10001];

int main(void){
  cin >> N;

  for(int i=1;i<=N;i++){
    cin >> arr[i];
  }

  
  dp[1] = 1;
  for(int i=2;i<=N;i++){
    dp[i] = 1;
    for(int j=1;j<i;j++){
      if(arr[i] > arr[j])
        dp[i] = max(dp[i], dp[j]+1);
    }
  }
  
  cout << *max_element(dp+1,dp+N+1);
  return 0;
  
}