백준 2167번 2차원 배열의 합

문제 링크입니다: https://www.acmicpc.net/problem/2167

요구사항이 살짝 모호했던 문제였습니다. 

처음에는 (i, j)~(x, y)까지의 배열의 합을 전부 구하는 문제인 줄 알았습니다.

여기서 진짜 요구하는 답은 행번호 i 이상 x 이하 그리고 열번호 j 이상 y 이하인 인덱스의 합이였습니다.

완전탐색법과 다이나믹 프로그래밍의 실행속도 차이가 명확하게 드러나는 문제였습니다.

/*

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오.

*/

//완전 탐색법

/*

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300 + 1;

int arr[MAX][MAX];

bool visited[MAX][MAX]; //각 인덱스를 한번만 더하기 위해

 

int N, M; //배열의 크기: 세로, 가로

int i, j, x, y; //좌표 (i,j)~(x,y)까지의 합

 

int arrSum(int curX, int curY) //currentX, currentY

{

        visited[curX][curY] = true;

        //해당 인덱스를 더하고

        int result = arr[curX][curY];

        //currentX가 i보다 크고 (currentX - 1, currentY)를 더한적이 없는 경우

        if (curX > i && !visited[curX-1][curY])

        {

               visited[curX - 1][curY] = true;

               result += arrSum(curX - 1, curY);

        }

        //currentY가 j보다 크고 (currentX, currentY - 1)을 더한적이 없는 경우

        if (curY > j && !visited[curX][curY - 1])

        {

               visited[curX][curY - 1] = true;

               result += arrSum(curX, curY - 1);

        }

        return result;

}

 

int main(void)

{

        cin >> N >> M;

        if (N < 1 || N >= MAX || M < 1 || M >= MAX)

               exit(-1);

 

        for (int i = 1; i <= N; i++)

               for (int j = 1; j <= M; j++)

                       cin >> arr[i][j];

 

        int K; //합을 구할 부분의 개수

        cin >> K;

        if (K < 1 || K>10000)

               exit(-1);

 

        for (int idx = 0; idx < K; idx++)

        {

               memset(visited, false, sizeof(visited));

               cin >> i >> j >> x >> y;

               if (i > x || j > y)

                       exit(-1);

               cout << arrSum(x, y) << endl;

        }

        return 0;

}

*/

 

//다이나믹 프로그래밍

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300 + 1;

int arr[MAX][MAX];

int cache[MAX][MAX];

 

int N, M; //배열의 크기: 세로, 가로

int i, j, x, y; //좌표 (i,j)~(x,y)까지의 합

 

int arrSum(void)

{

        cin >> i >> j >> x >> y;

        if (i > x || j > y)

               exit(-1);

        //(i, j) ~ (x, y)의 합을 구하므로

        //(1, 1) ~ (x, y)의 누적합에서 (1, 1) ~ (i-1, y)과 (1, 1) ~ (x, j-1)의 합을 뺌

        //여기서 중복되는 (1, 1) ~ (i-1, j-1)은 더해줌

        return cache[x][y] - cache[i - 1][y] - cache[x][j - 1] + cache[i - 1][j - 1];

}

 

int main(void)

{

        memset(arr, 0, sizeof(arr));

        memset(cache, 0, sizeof(cache));

        cin >> N >> M;

        if (N < 1 || N >= MAX || M < 1 || M >= MAX)

               exit(-1);

 

        for (int i = 1; i <= N; i++)

               for (int j = 1; j <= M; j++)

                       cin >> arr[i][j];

       

        //cache 초기화

        for(int i=1; i<=N; i++)

               for (int j = 1; j <= M; j++)

               {

                       cache[i][j] = arr[i][j];

                       //(1,1)     ... (1, temp)    ... (1, max)

                       //(temp, 1) ... (temp, temp) ... (temp, max)

                       //(max, 1)  ... (max, temp)  ... (max, max)

 

                       //이 경우 (1, 1) ~ (max, max)까지의 합은 (1, 1) ~ (temp, max) 과 (1, 1) ~ (max, temp)의 합

                       //여기서 (1, 1) ~ (temp, temp)은 중복되므로 하나 빼줌

                       cache[i][j] += (cache[i - 1][j] + cache[i][j - 1] - cache[i - 1][j - 1]);

               }

 

        int K; //합을 구할 부분의 개수

        cin >> K;

        if (K < 1 || K>10000)

               exit(-1);

       

        for (int idx = 0; idx < K; idx++)

               cout << arrSum() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~