[codeground] 52. 최대 직사각형

 

codeground - Practice - 연습문제 - 52. 최대 직사각형

문제 : https://www.codeground.org/practice/practiceProblemList

---

2차원 배열에서 만들 수 있는 모든 직사각형들의 배열 합 중 최대값을 구하는 문제다.

[그림 1]

직사각형을 [그림 1] 순서로 탐색하였다.

그런데 실제로는 1,2를 합친 것, 3,4를 합친 것, 5,6을 합친 것 또한 직사각형도 탐색을 해야 하므로 추가적인 알고리즘이 더 필요하다. 

[그림 2]

이를 위해 변수 2개를 사용한다.

tmp는 현재 탐색 중인 직사각형(빨간색)의 배열 합을 의미한다.

row는 현재까지 탐색한 열 범위([그림 2]에서 열 범위는 1~2)로 만들 수 있는 직사각형들 중 가장 큰 배열의 합을 의미한다.

[그림 3]

즉, [그림 3] 처럼 열의 크기와 범위는 일정하고 행의 크기가 1이상인 직사각형들을 뜻한다.

이제 지정된 열 범위로 행을 1부터 N까지 탐색하면서 해당하는 행의 tmp를 구하고 row를 갱신한다.

row는 이때까지 만든 직사각형에 현재 행을 합친 것과 현재 행만을 비교했을 때 배열 합이 큰 것으로 갱신한다.(row는 배열의 합이 가장 큰 직사각형을 저장하기 때문에)

 

모든 열의 범위로 모든 행을 탐색했을 때의 row의 값들 중 최대값이 정답이 된다.

 

열의 범위를 정하는데 O(N2)이 걸리고 그 범위에서 모든 행을 탐색하는데 O(N)이 소요된다.

따라서 총 시간복잡도는 O(N3)이 되고 N의 범위가 100보다 같거나 작으므로 시간내에 해결할 수 있는 알고리즘이다.

---

소스 코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/52.%20%EC%B5%9C%EB%8C%80%20%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95.cpp

---

소스 12번째 줄 maxnum은 배열의 모든 수가 0이거나 음수인 경우를 처리해주기 위해 만들었는데

36번째 줄 row = max(tmp, row + tmp) 에서 row의 default값이 0 이므로 모든 수가 0보다 작은 값이 들어가더라도 이 줄에서 체크할 수 있으므로 사실상 maxnum은 굳이 사용지는 않아도 된다.