BOJ-11660 구간 합 구하기 5 Swift

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

내가 푼 풀이

- 연산의 최대횟수가 100,000이고, 배열의 크기가 최대 1024이므로 단순히 주어진 연산의 범위만큼 반복문을 돌리면,

최악의 경우 연산횟수가 100,000 * 1024 * 1024나 되므로, 계산된값을 저장하고 이용하기로 했다.

- 주어진 (N+1) x (N+1) 크기의 배열 dp를 선언한다.

- 행과 열이 인덱스가 0인경우 0을 넣어준다.

- dp[i][j] = 1행 1열부터 i행 j열까지 더한 범위의 값이라고 정의하자.

- (x1, y1) , (x2, y2) 가 주어졌을때,

- 예시로 4 x 4 배열이 주어졌을때, (2, 2) (3,4)의 범위는 아래와같다.

 

0	0	0	0	0
0
0
0
0

이 범위의 연산결과는 아래처럼 나타낼 수 있다.

0	0	0	0	0
0
0
0
0

위의 큰 배열에서 

0	0	0	0	0
0
0
0
0

0	0	0	0	0
0
0
0
0

위 두가지 범위를 빼준 후

0	0	0	0	0
0
0
0
0

이 범위를 더해주면 된다.

 

이를  0,0부터 i,j까지의 연산범위합이 들어간 dp[i][j]를 이용하면 아래와 같이 나타낼 수 있다.

- dp[3][4] - dp[1][4] - dp[4][1] + dp[1][1] 

위 공식을 이용해서 연산결과들을 출력한다.

(x1, y1) , (x2, y2) 의 범위가 주어졌을때, 해당 범위의 연산결과는

dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 

 

import Foundation

var counts = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: counts[0] + 1)]
var dp = Array(repeating: Array(repeating: 0, count: counts[0] + 1), count: counts[0] + 1)
// 주어진 n x n 배열 저장
// (n+1) x (n+1) 크기로 저장하고, 행렬의 인덱스가 0이면 0 저장
for i in 0..<counts[0] {
    arr.append([0] + readLine()!.split(separator: " ").map{ Int($0)! })
}

// dp[i][j] = 0,0 부터 i,j까지 모두 합한 결과를 저장
for i in 1..<dp.count {
    for j in 1..<dp.count {
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
    }
}

// 해당 범위만큼의 연산결과 출력
for i in 0..<counts[1] {
    var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
    let x1 = inputs[0]
    let y1 = inputs[1]
    let x2 = inputs[2]
    let y2 = inputs[3]

    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])
}