[Algorithm] [Python & Swift] 백준/BOJ - 2167 _ 2차원 배열의 합

2167 - 2차원 배열의 합

 

문제

---

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

 

입력

---

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

 

출력

---

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

 

제출 코드

---

 

Swift

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let h = input[0]
let w = input[1]
var matrix = [[Int]]()
var dp: [[Int]] = Array(repeating: [Int](repeating: 0, count: w+1), count: h+1)
for _ in 0..<h {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    matrix.append(input)
}
for i in 1...h {
    for j in 1...w {
        dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    }
}
for _ in 0..<Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let i = input[0]
    let j = input[1]
    let x = input[2]
    let y = input[3]   
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])
}

 

Python

from sys import stdin
h, w = map(int, stdin.readline().split())
matrix = [list(map(int, stdin.readline().split())) for _ in range(h)]
dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1, h+1):
        for j in range(1, w+1):
            dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
for _ in range(int(stdin.readline())):
    i, j, x, y = map(int, stdin.readline().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

 

문제풀이

---

처음 파이썬으로 접근했을때 단순 for-loop을 이용해 문제를 풀어보려 했으나 시간초과가 났다. (pypy는 겨우겨우 통과..)

뭔가 좀 더 효율적인 방법을 찾아보려고 생각하다가 잘 생각이 안나서 다른사람의 풀이를 검색해봤다.

DP를 이용하신걸 보고 아차 싶어서 바로 DP로 풀어봤다.

2차원 배열의 합을 구하는 절차는 누적합을 이용하므로 누적합을 매번 계산할 필요없이 한번 계산한 결과는 저장해놓았다가 필요할 때 꺼내서 쓰면 된다.

한번 계산한 결과는 다시 계산하지 않고 가져다 쓴다 <- DP의 핵심 컨셉

matrix 입력을 받은 뒤, dp라는 배열을 생성한다.

이후, dp 배열 내부에 값을 채우는데 이때 dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] 공식을 따른다.