[백준 2631] - 줄 세우기(Kotlin)[골드4]

문제

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

2631번: 줄세우기

 

문제 풀이

문제는 정말 간단하다.

주어진 순서에서 최소한의 변경을 통해 오름차순으로 정렬하는 문제이다.

접근방법에 대해서 정말 많은 고민을 했었다.

최소한의 변경을 위해서는 기존 배열에서 최대한 고정시켜야 하는 부분을 길게 해야 한다고 이해했다.

그렇다면 고정시키는 번호를 어떻게 정할까?

문제 보기에서만 봐도 움직이는 번호들은 정해져 있는것을 보면 유추할 수 있다.

 

3 7 5 2 6 1 4 -> 1 2 3 4 5 6 7 로 가기 위해서 1,2,4,7을 변경시킨 것을 알 수 있다.

그러면 우리는 어째서 3,5,6은 가만히 있어야 했는가에 대해서 집중할 필요성이 있다.

 

문제의 정렬은 오름차순으로 정렬하는것이다.

그렇다면 이미 오름차순으로 정렬되어 있는 부분들은 가만히 놔두고, 그 사이사이를 변경하면 되지 않을까? 에서 출발한다.

3 7 5 2 6 1 4에서 오름차순으로 정렬되어 있는 부분집합은 굉장히 많다. 

우리는 이러한 부분집합 중 원소들이 증가하고 가장 긴 부분집합을 찾고 그 부분집합을 제외한 원소들의 위치만 변경하면 될 것이다.

3 7 5 2 6 1 4의 증가하는 부분집합은 다음과 같다.

• {3,7}
• {3,5,6}
• {3,6}
• {3,4}
• {5,6}
• {2,6}
• {2,4}
• {1,4}

이렇게 찾아보니 예제에서 왜 3,5,6을 제외하고 다른 번호들을 움직였는지 알 것이다.

문제에 적용해 보면 우리는 문제에서 주어진 수열 중 증가하는 부분집합 중 가장 긴 녀석을 찾아야 한다.

이러한 방법을 알고리즘에서 LIS라고 하는데, 나는 입력의 크기가 그렇게 크지 않기 때문에 N² 알고리즘을 사용했다.

• i번째 원소를 기준으로 잡고, j번째 원소를 탐색한다.
  • j번째 원소가 i번째 원소보다 클 경우 dp [j] = dp[i]+1이 될 것이다.
  • 하지만 다른 원소를 기준으로 j번째 원소의 집합의 길이가 더 클 수 있다.
  • 따라서 최종적인 점화식은 dp[j] = max(dp [j] , dp [i]+1)이 될 것이다.
• 이렇게 모든 dp의 값을 구하고 최댓값을 반환해서 번호의 길이에서 빼주면 된다.

예를 들어서 설명해 보겠습니다.

번호	3	7	5	2	6	1	4
DP	1	2	2	1	2	1	2

위 표는 3을 기준으로 업데이트한 dp 배열이다.

7은 가장 큰 수 이기에 dp 값의 변화가 없으므로 5를 기준으로 다시 설명해 보겠습니다.

번호	3	7	5	2	6	1	4
DP	1	2	2	1	3	1	2

바뀐 부분은 dp [6]이다. 기존 {3,5} 집합에서 {3,5,6}으로 바뀌었기에 길이가 3이 저장된다.

이러한 방식으로 끝까지 진행하면 된다.

 

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

class `2631` {

    lateinit var ary : Array<Int>
    lateinit var dp : Array<Int>
    init{
        input()
        print(ary.size-solution())
    }
    fun input(){
        val br = BufferedReader(InputStreamReader(System.`in`))
        var size = br.readLine().toInt()
        ary = Array(size, { 0 })
        dp = Array(size , { 1 })
        for(i in 0 until size){
            ary[i] = br.readLine().toInt()
        }
    }
    fun solution() : Int{
        for(i in 0 until ary.size){
            for(j in i+1 until ary.size){
                if(ary[i]<ary[j])
                    dp[j] = max(dp[j], dp[i]+1)
            }
        }
        return if(dp.isEmpty()) 0
        else dp.maxOrNull()!!
    }
}
fun main(){
    val solution = `2631`()
}