[백준] 15724 - 주지수

1. 문제

15724번: 주지수

2. 개요

1 x 1의 단위 행정구역을 묶어 하나의 거대 행정구역인 주지수를 만드려고 한다.

영토의 크기와 조사 범위가 주어질 때, 해당 구역에 사는 총 인구수를 구해 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

2차원 배열인 dp 테이블을 만든다. dp 테이블의 값은 (1,1) 부터 해당 인덱스까지의 직사각형 내부의 총 인구수로 채워준다.

(x1, y1) (x2, y2) 범위의 인구는 (0, 0) (x2, y2) - (0, 0) (x1-1, y2) - (0, 0) (x2, y1-1) + (0, 0) (x1-1, y1-1)으로 나타낼 수 있다. 따라서 위에서 채워넣은 dp테이블의 값을 이용하여 답을 구해 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

nums = []
dp = [[0 for i in range(M+1)] for j in range(N+1)]

for i in range(N):
    nums.append(list(map(int, sys.stdin.readline().split())))

    for j in range(M):
        dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + nums[i][j] - dp[i][j]

K = int(sys.stdin.readline())

for i in range(K):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])

3-3. C#

namespace boj_15724
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int[,] dp = new int[N + 1, M + 1];
            int[,] nums = new int[N, M];

            for (int i = 0; i < N; i++)
            {
                string[] row = sr.ReadLine().Split();

                for (int j = 0; j < M; j++)
                {
                    nums[i, j] = int.Parse(row[j]);
                    dp[i + 1, j + 1] = dp[i, j + 1] + dp[i + 1, j] + nums[i, j] - dp[i, j];
                }
            }

            int K = int.Parse(sr.ReadLine());
            for (int i = 0; i < K; i++)
            {
                input = sr.ReadLine().Split();
                int x1 = int.Parse(input[0]);
                int y1 = int.Parse(input[1]);
                int x2 = int.Parse(input[2]);
                int y2 = int.Parse(input[3]);

                sw.WriteLine(dp[x2, y2] - dp[x1 - 1, y2] - dp[x2, y1 - 1] + dp[x1 - 1, y1 - 1]);
            }

            sw.Close();
        }
    }
}