백준 1999 최대최소 파이썬

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

1999번: 최대최소

플레5 문제치고는 너무 쉬웠다...

이게 아직 데이터가 부족한 것인지 난이도 측정이 잘못된 것인지 아니면 파이썬이 개선돼 시간초과가 안나는 것인지 잘 모르겠지만 일단 AC를 받긴 받았다..

처음에는 그냥 함수 하나 만들면 될거 같아 행과 열을 입력 받으면 그곳만 탐색해 최댓값 - 최솟값을 return해주는 함수를 만들어 출력해줬다. 당연히 처음부터 시간초과가 날것이라 생각했으나 이게 뭐람?! 63%부분까지 올라가는 것이다. 그래서 시간을 좀 더 줄이기위해 질문으로 받은 i,j가 중복될 수 있음을 알고 처음에 dp배열을 만들어 i,j에 맞는 값들을 저장해두고 i,j를 입력받으면 O(1)의 시간 복잡도로 빼내는 작업을 해줬더니 AC를 받았다. (문제 분류인 자료구조, 세크먼트 트리, 덱를 사용하지 않고)

개인적인 생각으로 나중에 재채점해서 시간초과가 나거나 난이도 하락이 있을거 같다.

import sys

def find(i,j):#최댓값 - 최솟값
    maxs = -sys.maxsize#최댓값
    mins = sys.maxsize#최솟값
    for k in range(i,i+b):
        for l in range(j,j+b):
            maxs,mins = max(s[k][l],maxs),min(mins,s[k][l])
    return (maxs-mins)
input = sys.stdin.readline
n,b,k = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
for i in range(n-b+1):
    for j in range(n-b+1):
        dp[i][j]= find(i,j)#dp배열에 저장

for _ in range(k):
    i,j = map(int,input().split())
    print(dp[i-1][j-1])#출력