[BOJ] 11660번 : 구간 합 구하기 5(Go, Golang)

문제 링크 : 백준 11660번

[문제 접근]

범위는 1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000 이기 때문에 전부 탐색으로 구현하면 최악의 경우 1024 x 1024 x 100,000으로 시간초과가 난다.
따라서 나는 dp를 이용해서 풀었다.

1. dp배열에는 (1, 1)부터 (i, j)까지 합을 저장한다.
2. (1, 1) ~ (x2, y2)까지의 합에서 (1, 1) ~ (x1-1, y2) 와 (1, 1) ~ (x2, y1-1)를 빼준다.
3. 2번의 결과는 (1, 1) ~ (x1-1, y1-1)까지 합을 2번 빼주게 되므로 한 번 더해준다.
4. 최종적으로 dp[x2][y2] - (dp[x1-1][y2] + dp[x2][y1-1]) + dp[x-1][y-1]이 정답이게 된다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	r              = bufio.NewReader(os.Stdin)
	w              = bufio.NewWriter(os.Stdout)
	n, m, tmp      int
	x1, y1, x2, y2 int
	dp             [1025][1025]int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n, &m)
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			fmt.Fscan(r, &tmp)
			dp[i][j] = dp[i-1][j] + dp[i][j-1] + tmp - dp[i-1][j-1]
			// dp[i][j]에 (1, 1)부터 (i, j)까지 합을 저장
		}
	}

	for i := 0; i < m; i++ {
		fmt.Fscan(r, &x1, &y1, &x2, &y2)
		result := dp[x2][y2] - (dp[x1-1][y2] + dp[x2][y1-1]) + dp[x1-1][y1-1]
		fmt.Fprintln(w, result)
	}
}