백준 1451 직사각형으로 나누기 정답 참조

1. 중복 되는 것을 줄이기. 2. 중복 되는 것을 줄이기... 3. 사각형은 인덱스가 중요하므로, 이것을 어떻게 처리할 것인지, 메모하기 3. 이것을 머리속으로만 생각하려니까 정리가 잘 되지 않음. 4. 한번에 연습장에 정리를 한 다음에, 풀이하도록 합니다.

#include <iostream> using namespace std; int n, m, a[101][101]; long long Max = 0; long long sum(int sx, int sy, int ex, int ey) { long long ret = 0; for (int i = sy; i <= ey; i++) { for (int j = sx; j <= ex; j++) { ret += a[i][j]; } } return ret; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char tmp; cin >> tmp; a[i][j] = tmp - '0'; } } // 1번 case for (int i = 0; i < m - 2; i++) { for (int j = i + 1; j < m - 1; j++) { long long a = sum(0, 0, i, n - 1); long long b = sum(i + 1, 0, j, n - 1); long long c = sum(j + 1, 0, m - 1, n - 1); if (Max < a*b*c) Max = a*b*c; } } // 2번 case for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { long long a = sum(0, 0, m - 1, i); long long b = sum(0, i + 1, m - 1, j); long long c = sum(0, j + 1, m - 1, n - 1); if (Max < a*b*c) Max = a*b*c; } } // 3번 case for (int i = 0; i < m - 1; i++) { for (int j = 0; j < n - 1; j++) { long long a = sum(0, 0, i, n - 1); long long b = sum(i + 1, 0, m - 1, j); long long c = sum(i + 1, j + 1, m - 1, n - 1); if (Max < a*b*c) Max = a*b*c; } } // 4번 case for (int i = m - 1; i > 0; i--) { for (int j = 0; j < n - 1; j++) { long long a = sum(i, 0, m - 1, n - 1); long long b = sum(0, 0, i - 1, j); long long c = sum(0, j + 1, i - 1, n - 1); if (Max < a*b*c) Max = a*b*c; } } // 5번 case for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m - 1; j++) { long long a = sum(0, 0, m - 1, i); long long b = sum(0, i + 1, j, n - 1); long long c = sum(j + 1, i + 1, m - 1, n - 1); if (Max < a*b*c) Max = a*b*c; } } // 6번 case for (int i = n - 1; i > 0; i--) { for (int j = 0; j < m - 1; j++) { long long a = sum(0, i, m - 1, n - 1); long long b = sum(0, 0, j, i - 1); long long c = sum(j + 1, 0, m - 1, i - 1); if (Max < a*b*c) Max = a*b*c; } } cout << Max << '\n'; return 0; }