[알고리즘 문제 풀기] 2차원 배열의 합(2167)

1. 문제 풀이 아이디어

• 누적 합 배열을 생성하여 사각형 구간의 합을 계산하여 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new(Console.OpenStandardInput()))
using (StreamWriter sw = new(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);
    int[,] arr = new int[n + 1, m + 1];
    for (int i = 1; i <= n; i++)
    {
        split = sr.ReadLine().Split();
        for (int j = 1; j <= m; j++)
        {
            arr[i, j] = int.Parse(split[j - 1]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            arr[i, j] += arr[i, j - 1] + arr[i - 1, j] - arr[i - 1, j - 1];
        }
    }

    int k = int.Parse(sr.ReadLine());
    while (k > 0)
    {
        split = sr.ReadLine().Split();
        int i = int.Parse(split[0]) - 1;
        int j = int.Parse(split[1]) - 1;
        int x = int.Parse(split[2]);
        int y = int.Parse(split[3]);
        int sum = arr[x, y] - arr[x, j] - arr[i, y] + arr[i, j];
        sb.AppendLine(sum.ToString());
        k--;
    }
    sw.Write(sb);
}

3. 정리

• arr[i, j]에 (1,1)부터 (i,j)까지의 누적 합을 저장한다.

• arr[i, j] += arr[i, j - 1] + arr[i - 1, j] - arr[i - 1, j - 1]를 이용해 누적 합을 계산한다.

• 각 질의에 대해 (x, y)까지의 합에서 불필요한 부분을 빼고 중복된 영역을 더해 사각형 합을 구해 문제를 해결한다.