백준 2571. 색종이 - 3

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

2571번: 색종이 - 3

 

이전에 푼 문제인데 그때는 브루트포스 O(N^6) 방식으로 풀었다.

https://tose33.tistory.com/758

백준 2571. 색종이 - 3

 

이번에는 누적합으로 O(N^3) 이 되도록 풀어봤다.

 

1. 높이의 누적합을 구한다 

예제의 경우 대략 아래처럼 나올것이다. 

 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  1  1  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0 
 0  0  0  2  2  2  2  2  2  2  2  2  2  0  0  2  2  2  2  2  2  2  2  2  2  0  0  0  0  0  0 
 0  0  0  3  3  3  3  3  3  3  3  3  3  0  0  3  3  3  3  3  3  3  3  3  3  0  0  0  0  0  0 
 0  0  0  4  4  4  4  4  4  4  4  4  4  0  0  4  4  4  4  4  4  4  4  4  4  0  0  0  0  0  0 
 0  0  0  5  5  5  5  5  5  5  5  5  5  0  0  5  5  5  5  5  5  5  5  5  5  0  0  0  0  0  0 
 0  0  0  6  6  6  6  6  6  6  6  6  6  1  1  6  6  6  6  6  6  6  6  6  6  0  0  0  0  0  0 
 0  0  0  7  7  7  7  7  7  7  7  7  7  2  2  7  7  7  7  7  7  7  7  7  7  0  0  0  0  0  0 
 0  0  0  8  8  8  8  8  8  8  8  8  8  3  3  8  8  8  8  8  8  8  8  8  8  0  0  0  0  0  0 
 0  0  0  9  9  9  9  9  9  9  9  9  9  4  4  9  9  9  9  9  9  9  9  9  9  0  0  0  0  0  0 
 0  0  0 10 10 10 10 10 10 10 10 10 10  5  5 10 10 10 10 10 10 10 10 10 10  0  0  0  0  0  0 
 0  0  0  0  0 11 11 11 11 11 11 11 11  6  6  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0 12 12 12 12 12 12 12 12  7  7  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0 13 13 13 13 13 13 13 13  8  8  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0 14 14 14 14 14 14 14 14  9  9  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0 15 15 15 15 15 15 15 15 10 10  0  0  0  0  0  0  0  0  0  0  0

 

2. 모든 좌표들에 대해 오른쪽으로 이동하면서 (가로길이를 늘리면서) 넓이를 구한다.

예를들어 위에서 (10,3)을 기준으로 탐색한다고 생각하면, 이말은 (10,3)을 좌측 하단으로 하는 직사각형을 탐색한다는 것이다.

[10][3] = 10 이므로 가로 길이가 1일때 넓이는 (1 * 10) 이다.

[10][4] = 10 이므로 가로 길이가 2일때 넓이는 (2 * 10) 이다.

[10][5] = 10 이므로 가로 길이가 3일때 넓이는 (3 * 10) 이다.

...

[10][13] = 5 이다. 

그런데 우리가 현재 구하는건 (10,3)을 좌측하단으로 하는 직사각형이기 때문에 높이는 더 작은값인 5로 수정해야 직사각형이 된다.

따라서 가로 길이가 11일때는 (11 * 5) 이다.

 

이렇게 넓이를 계속 구해서 최댓값을 갱신해준다.