코드코도

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

Boj/Dynamic Programming

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

고도고도 고도고도 2021. 1. 25. 11:54
728x90

www.acmicpc.net/problem/11053

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

 

입력

첫째 줄에 수열 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중 반복문을 써야한다.

 

최종 코드는

 

728x90
0 Comments
댓글쓰기 폼