[BOJ/백준][Silver2] 11053. 가장 긴 증가하는 부분 수열(Kotlin)

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

---

접근방법

우선 input[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의(LIS) 길이를 담을 dp배열을 생성해준다

dp[0]는 input[0]를 마지막 값으로 가지는 LIS 길이이므로 1이된다

 

이중 for문을 이용해 input[i]가 이전값(input[j])보다 크다면 dp[i]값을 초기화해주는 방식이다

표를 이용해 차근차근 설명해보겠다(예제 입력이용)

 

i = 0일때는 수열이 10 하나이므로 dp[i]는 1이기때문에 반복문 범위에 넣지 않아도 된다.

(dp 배열 생성시 값을 1로 초기화해주기 때문)

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1

 

 

i = 1일때, input[i] = 20, 이전값은 10이므로 input[i]가 더 크다.

따라서 수열의 가장 마지막에 20이 올 수 있으므로 dp[i] = dp[j] + 1이 된다.

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1	2

 

 

i = 2일때, input[i] = 10이고 이는 이전값 10, 20보다 크지 않다.

따라서 input[2]가 수열의 마지막에 있을경우 길이는 1이다.

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1	2	1

 

i = 3일때, input[i] = 30이고 이전값 10과 20 뒤에 붙을 수 있다.

내부 for문을 통해 dp값 중 가장 큰 값에 +1 해준 것이 dp[i]가 되겠다

따라서 maxOf(dp[i], dp[j] +1)로 큰 값을 구해주었다

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1	2	1	3

 

i = 4일때, input[i] = 20이고 이전값 중 10보다 크기때문에 10 뒤에 붙을 수 있다.

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1	2	1	3	2

 

이쯤되면 다들 이해했을거라고 생각하고 마지막 i = 5일때 dp를 구해보자

i = 5일때, input[i] = 50이고, 이전값 중 10, 20, 30 뒤에 붙을 수 있다.

따라서 dp = 4

i	0	1	2	3	4	5
input[i]	10	20	10	30	20	50
dp[i]	1	2	1	3	2	4

---

코드

import java.util.*

fun main(){
    val sc = Scanner(System.`in`)
    val N = readLine()!!.toInt()
    val input = readLine()!!.split(" ").map{it.toInt()} 
    //dp[i] : input[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이
    val dp = IntArray(N){1}
    for(i in 1 until N){
        for(j in 0 until i){
            if(input[j] < input[i]) dp[i] = maxOf(dp[i], dp[j]+1)
        }
    } 
    println(dp.maxOrNull())
}

 

---

참고

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

최장 증가 부분 수열 - 나무위키