[Java] 백준 1999 - 최대최소

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

 

 

풀이

N의 크기 제한이 250 밖에 안돼서 O(N³ + KN)까지 가능.

max[r][c] =A[r][c], A[r][c + 1], A[r][c + 2], …, A[r][c + B - 1] 중 가장 큰 값

min[r][c] =A[r][c], A[r][c + 1], A[r][c + 2], …, A[r][c + B - 1] 중 가장 작은 값

 

위의 두 메모리제이션을 활용해서 각 질문마다 O(N²) 걸릴 부분행렬 탐색을 O(N)로 줄이는 것이 가능해짐.  

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
	public static final int MIN = -1;
	public static final int MAX = 251;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[][] A = new int[N + 1][N + 1];

		for (int r = 1; r <= N; r++) {
			st = new StringTokenizer(br.readLine());
			for (int c = 1; c <= N; c++) {
				A[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		int[][] max = new int[N + 1][N + 1];
		int[][] min = new int[N + 1][N + 1];

		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N - B + 1; c++) {
				int tempMax = MIN;
				int tempMin = MAX;

				for (int i = 0; i < B; i++) {
					if (A[r][c + i] >= tempMax) {
						tempMax = A[r][c + i];
					}

					if (A[r][c + i] <= tempMin) {
						tempMin = A[r][c + i];
					}
				}

				max[r][c] = tempMax;
				min[r][c] = tempMin;
			}
		}

		StringBuilder sb = new StringBuilder();

		while (K-- > 0) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			int maxVal = MIN;
			int minVal = MAX;

			for (int i = 0; i < B; i++) {
				maxVal = Math.max(maxVal, max[r + i][c]);
				minVal = Math.min(minVal, min[r + i][c]);
			}

			sb.append(maxVal - minVal).append('\n');
		}

		System.out.println(sb);
		br.close();
	}
}

 

후기

처음에는 메모리제이션 과정에서 투 포인터 써서 총 시간복잡도를 O(N²)까지 줄이는 게 가능하겠다 싶었는데, N이 250 이하인 걸 보고 그냥 편하게 반복문 돌렸다. 다른 사람들 풀이 보니 O(N⁴)까지 통과 된다는 것 같고 (이건 문제의 의도가 아닌 것 같긴 한데..), 그만큼 풀이가 다양한 문제였다.