[2167번] 2차원 배열의 합

문제 출처 :

https://www.acmicpc.net/problem/2167

알고리즘 분석 :

문제 해결에 필요한 사항

1. 2차원 Dynamic Programming

2. 면적을 구하는 방법

이 문제는 그림을 직접 그려 해결하였다면 쉽고 빠르게 해결할 수 있는 문제이다.

우선 DP를 통해 0,0 부터 N, M의 누적 값을 모두 구한다. 이 누적 값을 면적이라고 하겠다.

이 면적을 구하는 알고리즘은 아래 소스코드의 주석에 자세히 적어두었다.

그렇다면 아래 그림의 푸른 빗금 부분의 면적을 어떻게 구할 수 있을까?

우선 전체 넓이에서 필요없는 윗부분 및 필요없는 왼쪽 부분을 빼준다.

이때 빼주게 되면 0,0 ~ 1,2 부분을 2번 빼주는 것이 되므로, 이 부분만 한번 다시 더해주는 방식을 취한다.

이렇게 구해놓은 DP값을 이용하여 푸른색 빗금친 부분의 면적을 구할 수 있다.

<< 알아두기 >> 

만약 이 코드를 DP없이 그냥 면적을 더하는 방식을 취하게 된다면 테스트 케이스가 많아질수록 계속 새로 더해야 되기 때문에

결국 시간 초과를 받게 된다.

소스 코드 : 

#include <iostream>
 
using namespace std;
 
int map[301][301];
int DP[301][301];
 
int main()
{
    int y, x;
 
    scanf("%d%d", &y, &x);
 
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            scanf("%d", &map[i][j]);
 
    DP[0][0] = map[0][0];
 
    // x = 0일때 y축에 대한 값을 일단 DP[i][0] 에넣어둔다.
    /*
    2 3

    1 2 4
    8 16 32 이면

    1 * *
    9 * * 로 먼저 구해둔다
    */
 
    for (int i = 1; i < y; i++)
        DP[i][0] = map[i][0];
 
 
    // 각 배열마다의 가로 DP값
    for (int i = 0; i < y; i++)
    {
        for (int j = 1; j < x; j++)
        {
            DP[i][j] = DP[i][j - 1] + map[i][j];
        }
    }
 
    // 각 배열마다의 가로 DP값에서 세로 DP값까지 갱신
    for (int i = 1; i < y; i++)
    {
        for (int j = 0; j < x; j++)
        {
            DP[i][j] = DP[i-1][j] + DP[i][j];
        }
    }
 
    /*
    // DP 최종 값
    
    for (int i = 0; i < y; i++)
    {
        for (int j = 0; j < x; j++)
            cout << DP[i][j] << " ";

        cout << endl;
    }
    */
 
 
    int tCase;
 
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        int y1, x1, y2, x2;
 
        scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
        // 배열 번호에 편하게 쓰기 위해 1씩 뺀다.
        y1--, x1--;
        y2--, x2--;
 
 
        /* 
           >> 쓰레기 코드 <<
           애초에 DP배열을 1,1부터 시작했으면 Memory Assert를 방지 할 수 있었는데
           0,0부터 시작하는 바람에 DP[-1][] 같은 부분을 침범하게 되어
           그것을 방지하고자 아래 4개의 if else문을 만들었다.
        */
        int ans1, ans2, ans3, ans4;
 
        if (y2 < 0 || x2 < 0)
            ans1 = 0;
 
        else
            ans1 = DP[y2][x2];
 
        if (y1 - 1 < 0 || x2 < 0)
            ans2 = 0;
 
        else
            ans2 = DP[y1 - 1][x2];
 
        if (y2 < 0 || x1 - 1 < 0)
            ans3 = 0;
 
        else
            ans3 = DP[y2][x1 - 1];
 
        if (y1 - 1 < 0 || x1 - 1 < 0)
            ans4 = 0;
 
        else
            ans4 = DP[y1 - 1][x1 - 1];
            
        printf("%d\n", ans1 - ans2 - ans3 + ans4);
    }
    
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>