[백준(BOJ)] 11048 이동하기 - 스위프트 (Swift)

[Silver II] 이동하기 - 11048

문제 링크

성능 요약

메모리: 84876 KB, 시간: 236 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 23일 00:35:53

문제 설명

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

풀이

해당 문제는 이 전의 위치 중 최대값을 가진 부분을 불러오면 되는 DP 문제였습니다. dp[r][c]를 (r, c)일 때의 최대값이라고 정의한다면,
dp[x][y]의 값은 dp[x-1][y],dp[x][y-1], dp[x-1][y-1] 중 최대값과 미로의 (x,y)값을 더해주면 됩니다.

 

다음은 코드입니다.

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var maze = [[Int]]()

for _ in 0..<n {
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    maze.append(row)
}

var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)

for i in 1...n {
    for j in 1...m {
        dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + maze[i-1][j-1]
    }
}

print(dp[n][m])