[알고리즘] Java / 백준 / 직사각형으로 나누기 / 1451
[알고리즘] Java / 백준 / 직사각형으로 나누기 / 1451
문제
접근 방식
가장 중요한 개념은 직사각형을 단 3개로만 나눈다는 것 이라 생각한다
- 가로 혹은 세로로 나눌 모든 경우의 수를 생각한다 (가로는 N-1개, 세로는 M-1개로 나눌 수 있다)
- 나눈 후 두 직사각형에 대해 자르지 않을 직사각형 하나를 선택한다 (경우의 수 = 2)
- 자를 직사각형에 대해 가로 혹은 세로로 나눌 모든 경우의 수를 생각한다 (가로는 남은 직사각형의 행 -1, 세로 또한 남은 직사각형의 열 -1)
- 각각의 경우의 수에 대해 세 직사각형 안에 들어있는 수를 누적합 dp 를 통해 O(1)로 계산한 후 곱하여 최댓값을 구한다
누적 합
// 2차원 배열의 각각 위치는 이전 열 혹은 이전 행의 모든 값을 더한 값
dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
특정 직사각형 안의 누적 합 구하기
//x1, y1 부터 x2, y2까지의 직사각형 안의 수 합
value = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_1451 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long[][] map = new long[N+1][M+1];
for(int i=1;i<=N;i++) {
String line = br.readLine();
for(int j=1;j<=M;j++) {
map[i][j] = map[i][j-1] + map[i-1][j] - map[i-1][j-1] + (line.charAt(j-1) -'0');
}
}
long max = 0;
for(int i=1; i< N;i++) {
long basedown = map[N][M] - map[i][M];
for(int j=1;j<M;j++) {
long left = map[i][j];
long right = map[i][M] - map[i][j];
long mul = basedown * left * right;
if(max < mul) max = mul;
}
for(int j=1;j<i;j++) {
long up = map[j][M];
long mid = map[i][M] - map[j][M];
long mul = basedown * up * mid;
if(max < mul) max = mul;
}
long baseup = map[i][M];
for(int j=1;j<M;j++) {
long left = map[N][j] - map[i][j];
long right = map[N][M] - map[N][j] - map[i][M] + map[i][j];
long mul = baseup * left * right;
if(max < mul) max = mul;
}
for(int j=i+1;j<N;j++) {
long mid = map[j][M] - map[i][M];
long down = map[N][M] - map[j][M];
long mul = baseup * mid * down;
if(max < mul) max = mul;
}
}
for(int j=1; j< M;j++) {
long baseright = map[N][M] - map[N][j];
for(int i=1;i<N;i++) {
long up = map[i][j];
long down = map[N][j] - map[i][j];
long mul = baseright * up * down;
if(max < mul) max = mul;
}
for(int i=1;i<j;i++) {
long left = map[N][i];
long mid = map[N][j] - map[N][i];
long mul = baseright * left * mid;
if(max < mul) max = mul;
}
long baseleft = map[N][j];
for(int i=1;i<N;i++) {
long up = map[i][M] - map[i][j];
long down = map[N][M] - map[N][j] - map[i][M] + map[i][j];
long mul = baseleft * up * down;
if(max < mul) max = mul;
}
for(int i=j+1;i<M;i++) {
long mid = map[N][i] - map[N][j];
long right = map[N][M] - map[N][i];
long mul = baseleft * mid * right;
if(max < mul) max = mul;
}
}
System.out.println(max);
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 직사각형으로 나누기 / 1451), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-직사각형으로-나누기-1451저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)