[C#] 백준 11660번 문제풀이

문제번호: 11660

문제명: 구간 합 구하기 5

문제링크: https://www.acmicpc.net/problem/11660

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

오늘은 2차원 배열에서 구간 합 구하는 문제를 풀었습니다. 두 좌표가 주어질 때 그 좌표 구간의 숫자 합을 구하는 문제입니다.
이 문제를 처음 접근했을 땐 직접 순회하며 O(N)^2의 시간복잡도로 해결하려고 시도해 보았지만 시간초과로 인해 맞출 수 없었습니다. 그래서 공부를 해본 결과 이런 문제는 prefix라는 2차원 배열에서 구간합을 미리 계산해 둔 후 공식을 이용해 풀이한다는 것을 알 수 있었습니다.

미리 계산해둔 구간합이란 1,1부터 x.y까지의 구간합을 말합니다. 이렇게 입력을 받아서 prefix 2차원 배열에 미리 계산해 둔 구간합을 입력해 둡니다.

이제 미리 계산해 둔 구간합을 이용해 공식을 도입해서 두 좌표 사이의 구간합을 구해야 합니다.
핵심 아이디어는 다음과 같습니다.
1,1~ x, y의 구간합을 미리 계산해 두었으니 x1, y1 ~ x2,y2 구간합을 구하려면 1,1~ x,y의 구간합에서 x2, y1의 위쪽영역, x1, y2의 왼쪽영역을 삭제해 주는 겁니다. 마지막으로 중복된 1,1 좌표가 2번 삭제되었으니 한번 더해주면 됩니다.
정리해 보자면 구간합 공식은 prefix [x2, y2] - - prefix[y1 - 1, x2] - prefix[y2, x1 - 1] + prefix[y1 - 1, x1 - 1] 이 됩니다.

다음은 정답코드입니다.

public static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int N = NM[0];
    int M = NM[1];

    int[,] prefix = new int[N + 1, N + 1]; // 1,1부터 x,y까지의 구간 합을 담는다.
    for (int y = 1; y <= N; y++)
    {
        int[] row = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        for (int x = 1; x <= N; x++)
        {
            prefix[y, x] =
                row[x - 1] // 값
                + prefix[y - 1, x] // 위쪽영역 더하기
                + prefix[y, x - 1] // 왼쪽영역 더하기
                - prefix[y - 1, x - 1]; // 중복된 영역은 한번 빼기
        }
    }

    for (int i = 0; i < M; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

        int y1 = input[0];
        int x1 = input[1];

        int y2 = input[2];
        int x2 = input[3];

        int sum =
            prefix[y2, x2] // 중심
            - prefix[y1 - 1, x2] // 위쪽영역 제거 (x2인 이유는 가로를 1부터 x2까지 제거해야하기 때문,)
            - prefix[y2, x1 - 1] // 왼쪽 영역 제거 (위와 동일한 이유)
            + prefix[y1 - 1, x1 - 1]; // 중복제거된 부분 다시 추가

        sw.WriteLine(sum);
    }
}