https://www.acmicpc.net/problem/25589
문제요약
- 400 * 400 격자, 숫자
- 격자안에 정사각형 : 숫자의 합 - 격자의 개수^2
- 격자안에 정사각형을 두 개, 안겹치게 할때 최대값 구하기
접근법
- 대충 완전탐색으로 정사각형 두개를 구하려면 답이 안나옴
- 하나만 구해본다면... 이건 될 것 같음 : 좌표당 사이즈당 = 400 400 * 400
- 이런 이상한 문제는 어떻게 특징을 발견하던데????
- 정사각형 두 개가 있다고 치면, 특징이 뭘까???
- 서로 안 겹침
- 구역이 나눠짐
- 가로줄, 세로줄로 나눠짐 => 중요
- 세로줄로 나눴다 치고
- 왼쪽 최대 + 오른쪽 최대
- 한쪽 면의 최대를 구할 수 있을까??
- 한쪽 면의 최대 구하기
- 편의상 세로줄 x를 기준으로 왼쪽면에서 나올 수 있는 최대를 구해본다고 할때
- 세로줄 x - 1까지는 구했다고 치고
- 새로운 세로줄 x에 대해서 쭉 여행하면서, 그 점이 오른쪽 구석이 되는 모든 정사각형의 합을 구해볼 수 있음
- 정사각형 합은 사전 작업을 해놓으면 O(1) 시간에 구할 수 있음
- 정사각형의 크기는 1 ~ n까지 분포
- 이런 식으로 모두 구하면 점의 개수 * 크기 = n^3 시간이 걸림
- 오른쪽 면도 동일한 요령으로 구할 수 있음
- 구했다고 치면, 세로 줄 x를 기준으로 영역이 나눠진다고 쳤을때, 왼쪽 최대 + 오른쪽 최대가 세로줄 x에 대한 최대가 될 것임
- 세로줄은 1 ~ n - 1 까지
- 동일한 요령으로 가로줄도 가능
newbieski