[1890] 점프

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

1890번: 점프

풀이

동적 계획법 문제이다. 처음에는 깊이 우선 탐색으로 시도했으나 시간 초과가 발생. 동적 계획법 문제로 분류되어있는 걸 확인하고 난 후 고민했으나, 결국 다른 사람의 풀이과정을 이해하고 코드를 다시 작성하였다.

 

시간 초과 코드

import Foundation

let n = Int(readLine()!)!

var map = Array(repeating: [Int](), count: n)
for i in 0..<n{
    map[i] = readLine()!.split(separator: " ").map{Int($0)!}
}
var ans = 0

func dfs(x:Int, y:Int){
    if map[x][y]==0{
        if x==n-1 && y==n-1{
            ans += 1
        }
        return
    }
    let length = map[x][y]
    if x+length<n{
        dfs(x: x+length, y: y)
    }
    if y+length<n{
        dfs(x: x, y: y+length)
    }
}
dfs(x: 0, y: 0)
print(ans)

 

해결 코드

import Foundation

let n = Int(readLine()!)!

var map = Array(repeating: [Int](), count: n)
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 0..<n{
    map[i] = readLine()!.split(separator: " ").map{Int($0)!}
}

dp[0][0]=1
for x in 0..<n{
    for y in 0..<n{
        if map[x][y]==0 || dp[x][y]==0{continue}
        let nx = x + map[x][y]
        let ny = y + map[x][y]
        if nx<n{ dp[nx][y] += dp[x][y]}
        if ny<n{ dp[x][ny] += dp[x][y]}
    }
}
print(dp[n-1][n-1])