[백준/BOJ] 11053번: 가장 긴 증가하는 부분 수열

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

해설

문제의 제목을 보자마자 최장 증가 수열(LIS)를 사용해야겠다는 생각을 하였다.

최장 증가 수열에는 두가지 방법이 있는데, 이중 반복문을 이용하는 방법과 이분 탐색을 이용하는 방법이 있다.

나는 아직 이분 탐색으로 LIS 알고리즘을 구현하는 것을 이해하지 못해 이중 반복문을 통해 문제를 해결하였다.

 

하지만 시간복잡도를 보면 이분 탐색을 이용하는 방법이 O(NlogN)으로 O(N²)인 이중 반복문보다 효율적이다.

이분 탐색으로의 방법이 궁금하다면 한번 찾아보는 것을 추천한다.

 

이중 반복문으로 최장 증가 수열(LIS)를 구현하는 방법을 알아보자.

앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나가는데, 이 때 증가하는 순서대로 숫자를 고르면서 부분 수열의 길이가 최대 길이가 되도록 선택한다.

 

수열의 최대 길이를 저장할 dp배열이 있다 하자.

10, 20, 10, 30, 20, 50이 있을 때

dp[0] = 1 -> 10

dp[1] = 2 -> 10 20

dp[2] = 1 -> 10

dp[3] = dp[1] + 1 = 3 -> 10 20 30 (30은 20보다 크므로 dp[1]에 길이 1을 추가시켜준다.)

dp[4] = dp[0] + 1 = 2 -> 10 20 (위와 같이 20은 10보다 크므로 dp[0]에 길이 1이 추가된다.)

dp[5] = dp[3] + 1 = 4 -> 10 20 30 50 (30보다 크므로 그 뒤에 50이 붙은 길이가 된다.)

 

이처럼 각각의 최대 길이 수열을 구했다면 정렬을 시켜 dp[n-1]을 출력하면 된다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = IntArray(n)
    val st = StringTokenizer(readLine())
    repeat(n) { i -> arr[i] = st.nextToken().toInt() }
    val dp = IntArray(n)
    for(i in 0 until n) {
        if(dp[i] == 0) dp[i] = 1
        for(j in 0 until i) {
            if(arr[i] > arr[j]) {
                if(dp[i] < dp[j] + 1) dp[i] = dp[j] + 1
            }
        }
    }
    dp.sort()
    println(dp[n-1])
}