[BOJ/백준][Gold4] 14002. 가장 긴 증가하는 수열4(Kotlin)

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

 

 

문제

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

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

---

접근방법

11053. 가장 긴 증가하는 부분 수열의 응용문제로 수열을 출력하는 것만 설명하려고 한다.

(가장 긴 수열의 길이 구하는 자세한 설명은 앞의 링크 참고)

 

위의 문제는 가장 긴 증가하는 부분 수열의 길이를 출력하면 되는데

이번에는 가장 긴 증가하는 부분 수열도 출력해야한다.

문제를 봤을 때 별로 어려운게 없는 것 같은데 gold4 난이도라서 의아했다.

부분 수열의 길이를 저장해놓은 dp 배열이 있으니까

dp를 구하고 0부터 반복문 돌려서 cnt를 늘려가며 출력하면 되는거 아닌가?

 

첫번째 제출

import java.util.*

fun main(){
    val N = readLine()!!.toInt()
    val input = readLine()!!.split(" ").map{it.toInt()}
    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())
    var cnt = 1
    for(i in 0 until N){
        if(dp[i] == cnt){
            cnt++
            print("${input[i]} ")
        }
    }
}

결과는 틀렸다. 처음에는 왜 틀렸는지 몰랐다. 

문제에 있는 입출력과 똑같았기 때문,,,

 

이 코드의 반례는 다음과 같다

5
1 4 2 3 5

이렇게 입력이 주어지면 출력은 

4

1 4 3 5

 

자,, 이제 문제가 무엇인지 보일것이다...

가장 긴 증가하는 부분 수열은 1 2 3 5로 출력되어야 한다.

그런데 dp[1]과 dp[2]가 모두 2인데, 0부터 반복문을 돌리게 되면 앞에있는 4가 먼저 출력되고, 2는 출력되지 않게된다.

 

따라서 반복문을 0부터 시작하는 것이 아닌, 뒤에서부터 시작하면서 역추적해야하는 것이다!

뒤에서부터 추적하기 때문에 해당 수열값을 stack에 저장한 후에 추적이 완료되면 하나씩 꺼내면서 출력해주었다

 

예외케이스를 생각해낸다면 문제 자체는 어렵지 않은 것 같은데 예외케이스를 생각하는게 좀 어려웠다

---

코드

import java.util.*

fun main(){
    val N = readLine()!!.toInt()
    val input = readLine()!!.split(" ").map{it.toInt()}
    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)
        }
    }
    
    var cnt = dp.maxOrNull()
    println(cnt)
    val stack = Stack<Int>()
    for(i in N-1 downTo (0)){
        if(dp[i] == cnt){
            cnt--
            stack.push(input[i])
        }
    }
    
    while(stack.isNotEmpty()) {
        print("${stack.pop()} ")
    }  
}