백준 2643 색종이 올려 놓기 Kotlin (dp)

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

2643번: 색종이 올려 놓기

문제

크기가 모두 다른 직사각형 모양의 색종이가 여러 장 있다. 색종이를 하나씩 올려 놓아, 되도록 많은 장수의 색종이들을 쌓으려고 한다.

새로 한 장의 색종이를 올려 놓을 때는 지금까지 쌓아 놓은 색종이들 중 맨 위의 색종이 위에 올려놓아야 하며 아래의 두 조건을 모두 만족해야 한다.

• 조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.
• 조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.(색종이를 90˚돌려 놓을 수 있다.)

예를 들어, 아래의 그림 중에서 위의 두 조건을 모두 만족하는 경우는 (나)뿐이다.

색종이는 두 변의 길이로 표현된다. (3, 5)는 두 변의 길이가 각각 3과 5인 색종이를 나타낸다. 예를 들어, 다음과 같이 7장의 색종이가 주어졌다고 하자 : (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12) 위의 조건을 만족하면서 가장 많이 쌓을 수 있는 색종이들의 순서는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

입력으로 색종이들이 주어졌을 때, 위의 조건 1과 조건 2를 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다.

출력

쌓을 수 있는 최대 색종이 장수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 정렬

풀이

최장 증가 부분 수열 (LIS) 알고리즘으로 풀면 되는 dp 문제이다.

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

이 문제에 위 알고리즘을 적용하려면 우선 주어진 색종이를 정렬해야 한다.

정렬은 여려 방식으로 할 수 있고, 본인은 x,y중 큰 값을 Pair.first에, 작은 값을 Pair.second에 저장하고 first 순 오름차순, first가 같다면 second 순 오름차순으로 정렬하였다.

내림차순으로 해도 상관없고 내림차순으로 하면 문제의 컨셉에 가깝고, 오름차순으로 하면 LIS의 컨셉과 더욱 일치한다.

오름차순 정렬된 색종이가 예를 들어

18 13

20 15

라고 하자.

18,13 중에 어떤 값이 x고 어떤 값이 y인진 알 필요가 없다. 회전할 수 있으니까.

오름차순으로 정렬했으니 20,15 종이가 18,13 종이의 뒤에 올 수 있는지 확인하면 된다.

즉, 기준이 되는 i인덱스의 종이를 i 이전의 종이 (0 ~ i-1)에 쌓인 종이들 중 가장 많이 쌓인 종이의 값에 1을 더하면 가능한 가장 많이 쌓을 수 있게 된다.  

x값은 뒤(인덱스)에 있는 게 무조건 클 수 밖에 없다.

j 종이의 작은 값인 18과 i 종이의 작은 값인 15를 비교했을 때  i 종이의 작은 값이 더 크다.

즉, j와 i의 큰 값은 18, 20으로 i 종이의 한 변은 무조건 j보다 크고, i종이의 작은 값도 j종이의 작은 값 보다 크기 때문에  j 종이의 뒤에 i종이가 올 수 있다.

 

    for(i in 0 until n){
        for(j in 0 until i){
            if(input[i].second >= input[j].second){
                dp[i] = dp[i].coerceAtLeast(dp[j]+1)
            }
        }
        answer = answer.coerceAtLeast(dp[i])
    }

위의 식이 핵심인데,

dp[i]는 dp[0~j]의 최댓값 +1으로, 현재 i 종이를 검사할 때 증가하는 부분 수열을 의미한다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var input: Array<Pair<Int, Int>>
lateinit var dp: IntArray
fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    dp = IntArray(n){1}
    input = Array(n) {
        val tk = StringTokenizer(br.readLine())
        val a = tk.nextToken().toInt()
        val b = tk.nextToken().toInt()
        Pair(a.coerceAtLeast(b),a.coerceAtMost(b))
    }
    input.sortWith(compareBy<Pair<Int, Int>> {it.first}.thenBy { it.second } )
    //solve
    var answer=0
    for(i in 0 until n){
        for(j in 0 until i){
            if(input[i].second >= input[j].second){
                dp[i] = dp[i].coerceAtLeast(dp[j]+1)
            }
        }
        answer = answer.coerceAtLeast(dp[i])
    }
    //output
    write("$answer")

    close()
}