[Swift 알고리즘] 백준 11660 구간 합 구하기 5

○

다이나믹 프로그래밍, 누적 합 Silver1

백준 11660번 구간 합 구하기 5

시간은 한시간 넘게 걸린거같은데 한번만에 통과함 ㅎㅎ 

어떻게 계산해야될지 방법을 찾기만 하면 구현이 어렵진 않았음. 생각해내는건 쉽지않았음 ㅎㅎ (뻔한 말인가,,?)

누적 합과 DP의 경계가 살짝 모호하지만 행렬을 사용하니깐 공간에 값을 저장해나가는 게 누적합을 사용한 DP에 좀 더 가까운 것 같다는 느낌?  

//85696KB 584ms
let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = nm[0]
let m = nm[1]
var matrix: [[Int]] = [Array(repeating: 0, count: n+1)]

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    matrix.append([0] + input)
}

var dp = matrix
for i in 1...n {
    for j in 1...n {
        dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    }
}

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    let (x1,y1,x2,y2) = (input[0], input[1], input[2], input[3])
    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])
}