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

문제링크 : https://www.acmicpc.net/problem/1999

1999번: 최대최소

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, B, K;
int arr[251][251];
int result[251][251];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> B >> K;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=1; i<=N-B+1; i++)
    {
        for(int j=1; j<=N-B+1; j++)
        {   
            int maxV = 0;
            int minV = 251;
            for(int k=i; k<i+B; k++)
            {
                for(int l=j; l<j+B; l++)
                {
                    maxV = max(arr[k][l], maxV); //최대값
                    minV = min(arr[k][l], minV); //최소값
                }
            }
            result[i][j] = maxV-minV; //각 범위별 최대값-최소값 저장
        }
    }

    while(K--)
    {
        int q1, q2;
        cin >> q1 >> q2;
        cout << result[q1][q2] <<'\n';
    }
    return 0;
}

N * N 행열에서 B * B 행렬 만큼 현재 인덱스를 움직이면서 전부 탐색하여 최대값과 최소값을 저장하여, 이를 result 배열에 저장해준다. 

이때 범위밖으로 나가면 안되기에 처음 i와 j을  N-B+1 까지만 이동하여 i+B의 값과 j+B의 값이 N을 넘어가지 않도록 해준다.

 

i와 j이 현재 행렬의 위치이므로 현재 i, j 위치를 기준으로 +B 만큼 이동하며 최대값과 최소값을 저장한다.

따라서 result[i][j]은 i와 j을 시작으로 B만큼 탐색한 최대값과 최소값의 차이를 저장한 값이다.

 

예제의 경우 i가 1, j이 2인 경우 이므로 result[1][2]의 값을 출력하게 된다.