문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2747번 피보나치 수, 2748번 피보나치 수 2 (0) | 2018.02.22 |
---|---|
백준 11057번 오르막 수 (0) | 2018.02.22 |
백준 9465번 스티커 (0) | 2018.02.18 |
백준 2163번 초콜릿 자르기 (0) | 2018.02.16 |
백준 1699번 제곱수의 합 (0) | 2018.02.16 |