백준 1451 - 직사각형으로 나누기

1. 문제 정리
- n * m의 직사각형이 주어지며, 각 칸에는 한자리 정수가 주어진다.
- 입력받은 직사각형을 3개의 직사각형으로 나눈다.
- 각 나누어진 직사각형에 속해있는 정수의 합을 구하고, 그 합의 곱의 최대값을 출력한다.

2. 접근
- 처음에는 어떻게 접근해야할까를 한참 고민했다.
- 직사각형이 나누어질 수 있는 케이스를 나누어 완전탐색을 시행했다.

3. 풀이

#include<iostream> using namespace std; int n, m; int a[50][50]; long long ans = 0; long long sum(int sx, int sy, int ex, int ey){ long long ret = 0; for(int i = sx; i <= ex; i++){ for(int j = sy; j <= ey; j++){ ret += a[i][j]; } } return ret; } int main(){ scanf("%d %d", &n, &m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%1d", &a[i][j]); } } long long temp = 0; // case 1 for(int i = 0; i < n-2; i++){ for(int j = i+1; j < n-1; j++){ temp = sum(0, 0, i, m-1) * sum(i+1, 0, j, m-1) * sum(j+1, 0, n-1, m-1); if(temp > ans) ans = temp; } } // case 2 for(int i = 0; i < m-2; i++){ for(int j = i+1; j < m-1; j++){ temp = sum(0, 0, n-1, i) * sum(0, i+1, n-1, j) * sum(0, j+1, n-1, m-1); if(temp > ans) ans = temp; } } // case 3 for(int i = 0; i < n-1; i++){ for(int j = 0; j < m-1; j++){ temp = sum(0, 0, i, m-1) * sum(i+1, 0, n-1, j) * sum(i+1, j+1, n-1, m-1); if(temp > ans) ans = temp; } } // case 4 for(int i = 0; i < n-1; i++){ for(int j = 0; j < m-1; j++){ temp = sum(0, 0, i, j) * sum(0, j+1, i, m-1) * sum(i+1, 0, n-1, m-1); if(temp > ans) ans = temp; } } // case 5 for(int i = 0; i < m-1; i++){ for(int j = 0; j < n-1; j++){ temp = sum(0, 0, n-1, i) * sum(0, i+1, j, m-1) * sum(j+1, i+1, n-1, m-1); if(temp > ans) ans = temp; } } // case 6 for(int i = 0; i < n-1; i++){ for(int j = 0; j < m-1; j++){ temp = sum(0, 0, i, j) * sum(i+1, 0, n-1, j) * sum(0, j+1, n-1, m-1); if(temp > ans) ans = temp; } } printf("%lld", ans); }

- long long sum(int sx, int sy, int ex, int ey) : sx, sy를 좌표로 시작해 ex, ey로 끝나는 좌표까지를 직사각형으로 간주하여 내부의 모든 정수값의 합을 반환한다.
- 직사각형이 나누어질 수 있는 case 별로 나누어 최대값을 구해내는 완전탐색을 실행한다.
- 직사각형 나누기 케이스
    

4. 소감
오랜만에 푸는 BruteForce 문제이기도 하지만, 유독 BruteForce 문제에는 약한 모습이 보인다는 생각을 하였다. 다른 문제의 경우 어느정도 풀이가 정형화 되어 있고(특히 bfs 또는 DP) 익숙해질 수록 문제 푸는 속도가 많이 빨라지는 데 반해, 이러한 문제는 문제별 푸는 방식이나 접근 방식이 달라 좀 어려움을 겪는 것 같다.
앞으로는 이런 완전탐색 문제도 많이 접해서 접근 방식의 선택지를 넓힐 수 있도록 공부해야겠다.