백준 1965번 상자넣기 Kotlin

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

문제

---

생각하기

---

• DP 문제이다.

동작

i번 배열을 만들어서 N까지 배열 전체를 순회한다.

이후 j 반복문을 만든 후 i까지 반복하게 만들어서 현재 기준 i번째 배열 상자 사이즈보다 작은 값의 경우 해당 상자의 최대값 + 1과 현재 memo[i]에 저장되어 있는 최대값이랑 비교해서 큰 값을 저장한다.

이 과정을 반복하며 가장 큰 값을 찾으면 된다.

결과

코드

---

TopDown

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private lateinit var memo: IntArray
private lateinit var arr: IntArray
private var N = 0

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    var ans = 1
    for (i in N - 1 downTo 0) {
        ans = ans.coerceAtLeast(LIS(i))
    }

    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun LIS(i: Int): Int {
    if (memo[i] != -1) return memo[i]

    memo[i] = 1
    for (j in 0 until i) {
        if (arr[j] < arr[i]) {
            memo[i] = memo[i].coerceAtLeast(LIS(j) + 1)
        }
    }

    return memo[i]
} // End of LIS()

private fun input() {
    N = br.readLine().toInt()

    arr = IntArray(N)
    memo = IntArray(N) { -1 }
    StringTokenizer(br.readLine()).let {
        for (i in 0 until N) {
            arr[i] = it.nextToken().toInt()
        }
    }
} // End of input()

BottomUp

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private lateinit var memo: IntArray
private lateinit var arr: IntArray
private var N = 0

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(bottomUp())
    return sb.toString()
} // End of solve()

private fun bottomUp(): Int {
    var ans = 1

    for (i in 0 until N) {
        memo[i] = 1
        for (j in 0 until i) {

            if (arr[j] < arr[i]) {
                memo[i] = Math.max(memo[i], memo[j] + 1)
            }
        }

        ans = ans.coerceAtLeast(memo[i])
    }

    return ans
} // End of bottomUp()

private fun input() {
    N = br.readLine().toInt()

    arr = IntArray(N)
    memo = IntArray(N)
    StringTokenizer(br.readLine()).let {
        for (i in 0 until N) {
            arr[i] = it.nextToken().toInt()
        }
    }
} // End of input()