[백준 kotlin] 3372 보드 점프

문제

 

보드게임에서 목표지점까지 도달할 수 있는 경우의 수를 구하는 문제이다.

---

풀이

DP를 사용하여 해결할 수 있는 문제이다.

Dp배열의 각 원소는 해당 지점까지 갈 수 있는 경우의 수로 구분된다.

 

for (i in 0 until N) {
    for (j in 0 until N) {
        val right = matrix[i][j] + j
        val down = matrix[i][j] + i

        if (matrix[i][j] == 0) continue

        if (right < N) {
            dp[i][right] = dp[i][j] + dp[i][right]
        }
        if (down < N) {
            dp[down][j] = dp[i][j] + dp[down][j]
        }


    }
}

 

그 후 보드게임을 순회하며 dp배열을 채운다.

먼저 보드게임에 적혀있는 숫자 만큼 오른쪽 또는 아래로 이동할 수 있으므로 

이동될 오른쪽 좌표와 아래 좌표를 계산한다.

 

그 후 만약 현재 위치의 dp값이 0이라면 해당 위치는 도달할 수 없는 위치이므로 반복문을 스킵한다.

아니라면 계산된 위치가 보드게임 내부임을 검사한 뒤 만약 내부라면 현재위치에 도달할 수 있는 값과 계산된 위치에 도달할 수 있는 값을 합쳐준다.

 

 

println(dp[N - 1][N - 1])

마지막으로 dp배열의 마지막 값을 출력하면 해당 값이 마지막 위치까지 도달할 수 있는 경우의 수가 된다.

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.math.BigInteger


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    val N = readLine().toInt()

    val matrix = mutableListOf<List<Int>>()
    repeat(N) {
        matrix.add(readLine().split(" ").map { it.toInt() })
    }

    val dp = Array(N) { Array(N) { BigInteger.ZERO } }

    dp[0][0] = BigInteger.ONE

    for (i in 0 until N) {
        for (j in 0 until N) {
            val right = matrix[i][j] + j
            val down = matrix[i][j] + i

            if (matrix[i][j] == 0) continue

            if (right < N) {
                dp[i][right] = dp[i][j] + dp[i][right]
            }
            if (down < N) {
                dp[down][j] = dp[i][j] + dp[down][j]
            }


        }
    }

    println(dp[N - 1][N - 1])
}