[알고리즘 문제 풀기] 구간 합 구하기 5(11660)

1. 문제 풀이 아이디어

• 2차원 배열의 누적 합을 미리 계산하여 구간 합을 빠르게 구한다.

2. 나의 정답 코드

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

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(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, n + 1];
    for (int i = 1; i <= n; i++)
    {
        split = sr.ReadLine().Split();
        for (int j = 1; j <= n; j++)
        {
            arr[i, j] = int.Parse(split[j - 1]) + arr[i, j - 1] + arr[i - 1, j] - arr[i - 1, j - 1];
        }
    }
    for (int i = 0; i < m; i++)
    {
        int[] xy = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        sb.AppendLine((arr[xy[2], xy[3]] - arr[xy[2], xy[1] - 1] - arr[xy[0] - 1, xy[3]] + arr[xy[0] - 1, xy[1] - 1]).ToString());
    }
    sw.Write(sb);
}

3. 정리

• arr[i, j]에 (1,1)부터 (i,j)까지의 합을 저장하는 누적 합 배열을 만든다.

• 누적 합을 활용하여 (x1, y1)부터 (x2, y2)까지의 합을 arr[x2, y2] - arr[x2, y1-1] - arr[x1-1, y2] + arr[x1-1, y1-1]로 계산해 문제를 해결한다.