[Kotlin][Alogrithm] 14391 - 종이조각

문제 요약

n * m 직사각형 종이를 크기가 세로나 가로 크기가 1인 직사각형 모양으로 자를 수 있을 때 종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하는 문제

1 <= n,m <= 4 이다.

문제 접근

브루트포스

n과 m은 최대 4이다.
따라서 브루트포스임을 확신하였다.

종이를 잘랐을 때 나올 수 있는 모든 경우의 수에 대해서 값을 구해보면 된다.
그 방법만 떠올린다면 해당 문제는 어렵지 않은 문제이다.

나는 각 위치에 boolean을 저장하는 dirArr배열을 만들었다.
dirArr에 true이면 가로로 자른 다는 뜻이고 true이면 세로로 자른다는 뜻이다.

즉 모든 경우의 수로 true와 false를 입력하고 배열의 처음부터 탐색하며 true이면 가로로 계속 진행하면 다음 오른쪽에 있는 원소도 true라면 이어 붙이는 방식으로 문제를 해결 하였다.

코드

fun main() {
    val br = System.`in`.bufferedReader()
    val (n, m) = br.readLine().split(" ").map { it.toInt() }

    var answer = 0
    val board = Array(n) { br.readLine().toCharArray() }
    val dirBoard = Array(n) { BooleanArray(m) }
    
    
    // 현재 방향 dirBoar를 이용하여 값 체크
    fun check() {

        var sum = 0
        val visited = Array(n) { BooleanArray(m) }

        for (x in 0 until n) {
            for (y in 0 until m) {

                if (visited[x][y]) continue

                var now = ""
                
                if (dirBoard[x][y]) {
                    for (ny in y until m) {
                        if (dirBoard[x][ny] && !visited[x][ny]) {
                            visited[x][ny] = true
                            now += board[x][ny]
                        }else {
                            break
                        }
                    }

                } else {
                    for (nx in x until n) {
                        if (!dirBoard[nx][y] && !visited[nx][y]) {
                            visited[nx][y] = true
                            now += board[nx][y]
                        } else {
                            break
                        }
                    }
                }
                
                if (now.isNotEmpty()) {
                    sum += now.toInt()
                }
                
            }
        }
        answer = maxOf(answer, sum)
    }

    // 모든 경우로 true false 저장
    fun dfs(x : Int, y : Int, dir : Boolean) {

        dirBoard[x][y] = dir

        if (x == n - 1 && y == m - 1) {
            check()
            return
        }


        var ny = y + 1
        val nx = if (ny < m) x else {
            ny = 0
            x + 1
        }
        
        dfs(nx,ny,true)
        dfs(nx,ny,false)
    }

    dfs(0,0,true)
    dfs(0,0,false)

    println(answer)
}

배운점

문제를 좀 더 단순화 시킬 수 있는 능력을 길러야겠다.
초기에 방향을 저장하는 배열을 만드는 생각이 떠오르지 않았다.