[C++] BOJ(백준) 1999 최대최소

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

1999번: 최대최소

 

자료구조 문제다.

 

N x N 행렬에서 B x B 크기 만큼에서 최대 최소를 찾아 그 차를 구하는 것이다.

모든 질문에 대해 B의 크기가 같다는 것을 못 보고 DP를 활용해 각각 최대 최소를 저장하는 배열을 만들려 했다.

그러나 B의 크기가 항상 동일하다는 것을 알고 DP가 아니라는 것을 알았다.

 

범위의 크기를 보니 무지성으로 탐색을 해도 괜찮을 것 같았다.

주의할 점은 중복되는 질의가 존재할 수 있다는 점이다.

그래서 한 번 계산한 범위는 배열에 저장해두고 배열에 값이 존재하면 이미 계산한 값을 출력하도록 했다.

 

무지성 탐색도 두 가지 방법을 생각했다.

1. 질의마다 탐색

2. 모든 범위에 대해 탐색 후 질의에 맞춰 출력

 

두 경우 모두 중복된 계산은 하지 않기 때문에 1번의 경우가 시간이 좀 더 빨랐다.

(질문이 들어오지 않는 구간이 존재하기 때문)

 

2번의 경우 시간 복잡도가 O(n^4)인데

사실 최악의 경우는 125^4로 예상되는데 이 경우 2초를 초과한다.

최악의 경우가 테케로 없어서인지 통과는 했다.

 

#include <iostream>
using namespace std;

int n, b, k;
int board[250][250];
int arr[250][250];

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> b >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			arr[i][j] = -1;
		}
    
	while (k--) {
		int r, c;	cin >> r >> c;
		r--;
		c--;

		if (arr[r][c] >= 0) {
			cout << arr[r][c] << "\n";
			continue;
		}

		int mi = 250;
		int ma = 0;

		for (int ii = r; ii < r + b; ii++) {
			for (int jj = c; jj < c + b; jj++) {
				mi = min(mi, board[ii][jj]);
				ma = max(ma, board[ii][jj]);
			}
		}

		arr[r][c] = ma - mi;

		cout << ma- mi << "\n";
	}
}