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

 

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

---

 

 

제목에 나타나있듯이 가장 긴 증가하는 부분 수열(Logest Increasing Subsequence) 라고 불리우는 대표적인 LIS 알고리즘이다.

 

쉽게 말하면, 일정한 패턴을 가진 수열이 중복을 허용하지 않고 이전 값보다 큰 경우를 나타내는 수열이다.

문제에서 보았듯이, {10, 20, 10, 30, 20, 50} 이 있다면 {10, 20, 30, 50}이 정답이라고 볼 수 있다.

 

 

문제의 관건은 어떻게 10 -> 20 -> 10 에서 3번째에 나오는 10을 무시하고 다음 수열의 값을 바라볼 수 있냐는 것이다.

 

 

출력 조건은 조건에 만족하는 길이를 출력하면 되므로, 만족할 때마다 한 단계 씩 높여가면 되기 때문에

= 다이나믹 프로그래밍

 

 

 

 

점화식은 다음과 같다.

dp[i] = max(dp[i], dp[j]+1) if( arr[j] < arr[i] )

 

 

 

초기 상태 

10	20	10	30	20	50
1	1	1	1	1	1

 

1로 초기화해주는 이유는 각각의 위치에서의 길이가 1이기 때문이고,

문제의 핵심인 최장 길이를 구하기 위해 조건에 만족한다면 1씩 더해주도록 하기 위함이다.

 

 

 

i=1

10	20	10	30	20	50
1	2	1	1	1	1

 

바라보고 있는 값(i=1)에서 이전의 값보다 크다면, 이전의 값에서 +1 한 값을 대입한다.

 

 

i=2

10	20	10	30	20	50
1	2	1	1	1	1

 

바라보고 있는 값(i=2)에서 이전의 값보다 크지 않으므로, 변함이 없다.

 

 

i=3

10	20	10	30	20	50
1	2	1	3	1	1

 

바라보고 있는 값(i=3)에서 이전의 값들보다 크다면, 가장 큰 값 + 1을 대입한다.

 

여기서 이해가 되지 않는다면,

이를 쪼개서 살펴보도록 한다.

 

i=3, j=0

10	20	10	30	20	50
1 + 1	2	1	2	1	1

 

i=3, j=1

10	20	10	30	20	50
1	2 + 1	1	3	1	1

 

i=3, j=2

10	20	10	30	20	50
1	2	1 + 1	3 (3 > 2이므로 3이 저장)	1	1

 

 

 

i=4

10	20	10	30	20	50
1	2	1	3	2	1

 

 

i=5

10	20	10	30	20	50
1	2	1	3	2	4

 

 

결국, LIS는 배열 안의 최댓값임을 확인할 수 있다.

 

 

전체 코드는 다음과 같다.

 

 

import java.io.*
import kotlin.math.max

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    
    val dp = IntArray(n) {1}
    val arr = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    
    for(i in 1 until n) {
        for(j in 0 until i ) {
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    println(dp.max())
}