[동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

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

 

 

입력

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

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

출력

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

---

해결 방법

 

a[i]를 입력된 수열, dp[i]를 i번째까지 가장 긴 증가하는 부분 수열의 길이라고 가정한다.

 

우선 배열을 탐색할 필요가 있다.

기준 원소를 정하고 기준 원소의 앞부분을 탐색하면서 기준 원소보다 작은 원소의 개수를 count하면 된다.

 

반복문을 돌려서 이전 값이 현재 값보다 작은 경우, (a[i-1] < a[i])

i번째까지 가장 긴 증가하는 부분 수열의 길이가 저장된 dp를 +1 해준다. (dp[i] = max(dp[i], dp[i-1] + 1)

 

해결 과정

반복문을 탐색하는데 기준 원소를 정하고 나머지 원소를 탐색하는 방식이므로 2중 반복문을 써야한다.

 

최종 코드는