8035 : 쉬운 LIS
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 수열 $A$가 주어집니다. 이 수열의 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)의 길이를 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 20$
• $1 \le a_i \le 20$ (정수)
[제약 조건]
• $1 \le N \le 20$
• $1 \le a_i \le 20$ (정수)
입력 설명
첫째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 20$)
둘째 줄에 수열의 원소 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다. 각 원소는 $1$ 이상 $20$ 이하의 정수입니다.
둘째 줄에 수열의 원소 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다. 각 원소는 $1$ 이상 $20$ 이하의 정수입니다.
출력 설명
가장 긴 증가하는 부분 수열의 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 4 2 4 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
$dp[i]$를 $a_i$를 마지막 원소로 갖는 증가 부분 수열 중 최대 길이라고 합시다. 모든 $dp$ 값을 $1$로 초기화한 후, 각 $i$에 대해 $i$ 이전의 인덱스 $j$ ($j < i$)들을 탐색하며 $a[j] < a[i]$인 조건이 성립할 때 $dp[i] = \max(dp[i], dp[j] + 1)$로 값을 갱신합니다. 최종적으로 $dp$ 배열의 최대값이 답이 되며, 시간 복잡도는 $O(N^2)$ 입니다. ($N \le 20$이므로 매우 빠르게 동작합니다.)