백준 2571. 색종이 - 3

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

2571번: 색종이 - 3

 

모든 0이 아닌 좌표 (검정 색종이가 있는 좌표)에 대하여 1x1 크기 부터 100x100 크기의 사각형이 만들어 질수 있는지 확인하고, 만들어 진다면 최댓값을 갱신하면 된다.

 

 

 

---

다른 분들 코드를 봤는데 누적합을 이용한 더 효율적인 풀이 방법이 있었다.

내가 먼저 풀이한 방법은 모든 좌표들에 대하여 O(N^2), 모든 크기에 대하여 O(N^2), 사각형 만들어지는지 여부 O(N^2) 를 확인하기 때문에 총 시간복잡도는 빅오로 O(N^6)이 된다.

 

누적합을 이용한 풀이는 다음과 같다. 

1. 먼저 세로의 누적합을 구한다. 

	1	1	1	1	1	1	1	1
	2	2	2	2	2	2	2	2
	3	3	3	3	3	3	3	3
	4	4	4	4	4	4	4	4
	5	5	5			5	5	5
	6	6	6			6	6	6
	7	7	7

 

하나의 좌표를 기준으로 가장 큰 높이값을 구하고, 오른쪽으로 이동하면서 최대 높이를 갱신한다.

(0,1)을 기준으로 잡으면 가장 큰 높이가 맨 아래 있는 값 7이다.

이제 오른쪽으로 가면서 4열에서 최대 높이가 4가 되기 때문에 최대 높이를 4로 갱신해준다. 

6열에서 최대 높이 6을 만나지만 더 큰 값으로 갱신할수는 없다. 

따라서 직사각형은 (0,0) 부터 (3,8)이 된다.