on
백준 12015 가장 긴 증가하는 부분 수열 2 Kotlin (dp)
백준 12015 가장 긴 증가하는 부분 수열 2 Kotlin (dp)
반응형
문제 출처 : https://www.acmicpc.net/problem/12015
문제
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
비슷한 문제
알고리즘 분류
풀이
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]
반응형
from http://ongveloper.tistory.com/232 by ccl(A) rewrite - 2021-09-10 17:27:12