[BOJ] 10803 정사각형 만들기 - P3

문제풀이

1. 가로, 세로로 쪼갰을 때 나오는 두 부분의 최소값을 구하는 dp테이블을 만든다.
2. 한쪽의 길이가 다른쪽의 길이보다 많이 클 때 (n >> m), 작은 쪽의 길이를 한 변의 길이로 하는 정사각형(m x m)을 만드는 것이 가장 최소가 된다. dp[n][m] = 1+ dp[n-m][m] (그리디)

---

주의사항

1. 일반적인 dp로 구현하면 시간 초과를 피할 수 없다.

---

소요시간

40분

---

package 백준.Platinum.P3.p10803_정사각형자르기

import kotlin.math.min

const val IMPOSSIBLE = Int.MAX_VALUE
fun main() {
    val (n, m) = readln().split(" ").map(String::toInt)
    val dp = Array(n + 1) { IntArray(m + 1) { IMPOSSIBLE } }
    for (r in 1..n) {
        for (c in 1..m) {
            if (r >= c && r % c == 0) dp[r][c] = r / c
            if (r < c && c % r == 0) dp[r][c] = c / r
        }
    }
    fun dp(r: Int, c: Int): Int {
        if (dp[r][c] != IMPOSSIBLE) return dp[r][c]
        if (r >= c * 3) return 1 + dp(r - c, c)
        if (c >= r * 3) return 1 + dp(r, c - r)
        var minCount = IMPOSSIBLE
        for (i in 1..(r / 2)) {
            minCount = min(minCount, dp(i, c) + dp(r - i, c))
        }
        for (i in 1..(c / 2)) {
            minCount = min(minCount, dp(r, i) + dp(r, c - i))
        }
        return minCount.also { dp[r][c] = it }
    }
    println(dp(n, m))
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P3/p10803_%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95%EC%9E%90%EB%A5%B4%EA%B8%B0/p10803_%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95%EC%9E%90%EB%A5%B4%EA%B8%B0.kt

---

문제링크

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

---

회고

무조건 시간 초과가 나오는 코드에서 어떻게 하면 시간을 줄일 수 있을까 고민을 많이 했다. 결과적으로는 한 쪽의 길이가 길게 나온 이유가 있었다. 한쪽의 길이가 다른쪽의 길이보다 월등히 크면, 정사각형을 하나 만들어 놓고 시작하는 것이 가장 최소가 되는 방법이다.