백준 11053 가장 긴 증가하는 부분수열

문제보기

부분수열 문제이다. 

그리고 동적계획법이지만 이것은 LIS풀이가 적용되었다. 

'수열 A가 주어졌을때, 가장 긴 증가하는 부분수열을 구하라'  이다.

즉, 수열마다 이게 몇번째 수열인지 최대값으로 체크한다. 

수열이 존재할때 각각의 위치의 해석은 

A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이이다.

조건은 이러하다

A[i]가 있을때, i 보다 작은 index들(ex. 0~j)의 값들을 A[i]와 비교한다. 그리고 A[i]가 A[j]가 '증가하는 수열'이므로 길이를 비교한다.

조건 : j<i , A[j] < A[i] 

또 하나의 조건이 더 있다. 만약 D[i]가 4인데, D[j]가 2이면 A[j]와 A[i]가 부분수열이여도 길이를 바꿔줄 필요가 없다. 

그래서 이러한 조건이 붙는다. 

D[i] < D[j]+1

끝이다. 코드를 보면 이해가 될 것이다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39