[BOJ/JAVA] 백준 1451 : 직사각형으로 나누기 (자바)

문제 정보

  문제명   - 직사각형으로 나누기
  난이도   - 골드 V
문제 번호 - 1451번

---

문제 링크

BOJ_G5_1451_직사각형으로_나누기

1451번: 직사각형으로 나누기

---

문제

세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.
세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.
어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

---

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다.
둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

---

출력

세 개의 작은 직사각형의 합의 곱의 최댓값을 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
1 8 11911103	108
3 3 123 456 789	3264
3 1 7 9 3	189

---

알고리즘 분류

● 브루트포스 알고리즘
● 누적 합
● 많은 조건 분기

---

소스코드

package Lv3_Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 브루트포스 알고리즘, 누적 합, 많은 조건 분기
 * https://www.acmicpc.net/problem/1451
 */
public class BOJ_G5_1451_직사각형으로_나누기 {
	static long result = Long.MIN_VALUE;
	public static int sumRang(int Row_start, int Row_end, int Col_start, int Col_end, int[][] num) {
		int sum = 0;
		for (int i = Row_start; i < Row_end; i++)
			for (int j = Col_start; j < Col_end; j++)
				sum += num[i][j];
		return sum;
	}
	public static void Row(long multi, int row_start, int N, int col_start, int M, int[][] num) {
		for (int i = row_start+1; i < N; i++) {
			long tmp = multi;
			tmp *= sumRang(row_start, i, col_start, M, num);
			tmp *= sumRang(i, N, col_start, M, num);
			result = Math.max(result, tmp);
		}
	}
	public static void Col(int multi, int row_start, int N, int col_start, int M, int[][] num) {
		for (int i = col_start+1; i < M; i++) {
			long tmp = multi;
			tmp *= sumRang(row_start, N, col_start, i, num);
			tmp *= sumRang(row_start, N, i, M, num);
			result = Math.max(result, tmp);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		// NxM 크기의 직사각형
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		// 직사각형의 데이터 입력
		int[][] num = new int[N][M];
		for (int i = 0; i < N; i++) {
			char[] tmp = br.readLine().toCharArray();
			for (int j = 0; j < M; j++)
				num[i][j] = Integer.parseInt(tmp[j] + "");
		}
		for (int i = 1; i < N; i++) {
			int sum = sumRang(0, i, 0, M, num);
			// 세로 + 세로 + 세로
			Col(sum, i, N, 0, M, num);
			// 세로 + 가로 + 가로
			Row(sum, i, N, 0, M, num);
		}
		for (int i = N-1; i > 0; i--) {
			int sum = sumRang(i, N, 0, M, num);
			// 역방향 세로 + 가로 + 가로
			Col(sum, 0, i, 0, M, num);
		}
		for (int i = 1; i < M; i++) {
			int sum = sumRang(0, N, 0, i, num);
			// 가로 + 가로 + 가로
			Row(sum, 0, N, i, M, num);
			// 가로 + 세로 + 세로
			Col(sum, 0, N, i, M, num);
		}
		for (int i = M-1; i > 0; i--) {
			int sum = sumRang(0, N, i, M, num);
			// 역방향 가로 + 세로 + 세로
			Row(sum, 0, N, 0, i, num);
		}
		System.out.println(result);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---