백준 12015 가장 긴 증가하는 부분 수열 2 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/12015

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

비슷한 문제

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11055번. 가장 큰 증가 부분 수열
• 11722번. 가장 긴 감소하는 부분 수열
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4
• 14003번. 가장 긴 증가하는 부분 수열 5

알고리즘 분류

• 이분 탐색
• 가장 긴 증가하는 부분 수열: o(n log n)

풀이

2021.04.20 - [알고리즘 문제 풀이/백준] - 백준 11054 가장 긴 바이토닉 부분 수열 c++

2021.04.19 - [알고리즘 문제 풀이/백준] - 백준 11053 가장 긴 증가하는 부분 수열 c++,Kotlin (dp)

 

가장 긴 증가하는 부분 수열의 시리즈 문제이다,

위의 11053은 dp를 만드는 과정에서 O(N^2)의 시간 복잡도여도 N이 1000이었기 때문에 통과하였지만,

이번 문제는 N이 1000000이기 때문에, O(N^2)의 시간 복잡도로는 통과할 수 없다.

따라서 dp를 만드는 과정에서 시간 복잡도를 줄여야 하는데, dp[1~n]의 값을 구해야 하므로 N의 시간 복잡도는 필연적이고, dp[1~n]에 들어가는 숫자를 탐색하는 과정을 선행 탐색이 아닌 이분 탐색으로 시간 복잡도를 줄여 O(NlogN)으로 통과할 수 있다.

 

주어진 예제 

6

10 20 10 30 20 50에서,

 

dp[0]= 10 //비교할 대상이 없음 초기값

dp = {10}

 

arr[1]이 dp[0]보다 크기 때문에 그대로 dp의 맨 뒤에 arr[1]을 추가한다.

dp[1]=arr[1]

dp = {10, 20}

 

arr[2]이 dp[1]보다 작기 때문에 dp[0]~dp[1]의 값중에서 arr[2]가 들어갈 위치를 이분 탐색으로 찾아서 넣는다. dp[0]=arr[2]

dp = {10, 20}

 

arr[3]이 dp[1]보다 크기 때문에 그대로 dp의 맨 뒤에 arr[3]을 추가한다.

dp[2] = arr[3]

dp = {10, 20, 30}

 

arr[4]이 dp[2]보다 작기 때문에 dp[0]~dp[2]의 값중에서 arr[4]가 들어갈 위치를 이분 탐색으로 찾아서 넣는다.

dp[1] = arr[4]

dp = {10, 20, 30}

 

arr[5]이 dp[2]보다 크기 때문에 그대로 dp의 맨 뒤에 arr[5]을 추가한다.

dp[3] = arr[5]

dp = {10, 20, 30, 50}

 

이후, dp의 길이를 출력하면 된다.

  

 

코드

import java.util.*
fun biSearch(dp : IntArray ,find : Int, start : Int, end : Int) : Int{
    var mid = (start+end)/2
    if(start==end){
        return mid
    }
    if(find>dp[mid]){
        return biSearch(dp,find,mid+1,end)
    }
    else if(find==dp[mid]){
        return mid
    }
    else{
        return biSearch(dp,find,start,mid)
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = Integer.parseInt(br.readLine())
    val arr = IntArray(n)
    val dp = IntArray(n)
    val tk = StringTokenizer(br.readLine())
    var idx=0
    arr[0] = Integer.parseInt(tk.nextToken())
    dp[0]=arr[0]
    for(i in 1 until n){
        arr[i] = Integer.parseInt(tk.nextToken())
        if(dp[idx]<arr[i]){
            dp[++idx]=arr[i]
        }
        else {
            dp[biSearch(dp, arr[i], 0, idx)] = arr[i]
        }
    }
    var answer = dp.indexOfFirst { it==0 }
    if(answer==-1){
        write("${dp.size}")
    }
    else{
        write("$answer")
    }
    close()
}