[백준] 점프 (1890)(kotlin)

문제 설명

백준 1890번 문제 링크

입력 및 출력

» 입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

» 출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입출력(테스트케이스)

입력	출력
4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0	3

문제 풀이1

풀이 참고

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val map = Array(N) {
        readLine().split(" ").map { it.toInt() }.toIntArray()
    }
    val dp = Array(N) { LongArray(N) }

    dp[0][0] = 1

    for (y in 0 until N) {
        for (x in 0 until N) {
            if (y == N - 1 && x == N - 1) continue

            if (y + map[y][x] < N) {
                dp[y + map[y][x]][x] += dp[y][x]
            }
            if (x + map[y][x] < N) {
                dp[y][x + map[y][x]] += dp[y][x]
            }
        }
    }

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