[백준] 24392번. 영재의 징검다리(Kotlin)

문제

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

---

풀이(15분)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

/*
    DP를 이용해 경로 수 계산
    - map[i][j] : 해당 칸이 방문 가능한지 (1이면 true)
    - dp[i][j]  : (0,0)부터 (i,j)까지 오는 경로 수
    - 방향: 왼쪽 위, 위, 오른쪽 위
    - 최종 답: 마지막 행의 dp 합
*/
var N = 0
var M = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())

    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    // 지도 및 DP 배열 초기화
    val map = Array(N) { Array(M) { false } }
    val dp = Array(N) { Array(M) { 0 } }

    // map 입력 처리 (1이면 true)
    repeat(N) { i ->
        val line = StringTokenizer(br.readLine())
        repeat(M) { j ->
            map[i][j] = line.nextToken().toInt() == 1
        }
    }

    // 첫 번째 행 초기화
    repeat(M) { j ->
        if (map[0][j]) dp[0][j] = 1
    }

    // DP 진행
    for (i in 1 until N) {
        for (j in 0 until M) {
            if (!map[i][j]) continue

            // 왼쪽 위
            if (isBound(i - 1, j - 1)) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % 1_000_000_007
            // 바로 위
            if (isBound(i - 1, j)) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % 1_000_000_007
            // 오른쪽 위
            if (isBound(i - 1, j + 1)) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % 1_000_000_007
        }
    }

    // 마지막 행 합 계산
    val cnt = dp[N - 1].fold(0L) { acc, value -> (acc + value) % 1_000_000_007 }.toInt()

    println(cnt)
}

// 배열 경계 체크
fun isBound(x: Int, y: Int): Boolean = x in 0 until N && y in 0 until M

---

문제 풀이 전략

 

위에서 아래로 이동하나 아래에서 위로 이동하나 정답이 바뀌는 것은 아니므로 위에서 아래로 내려가는 것으로 계산했다.

 

DP를 통해 이 전 위치에서의 값을 누적해 가는 방식을 사용했다.