백준 20002 사과나무

https://www.acmicpc.net/problem/20002

문제

N * N의 크기를 가진 사과나무에서 정사각형 크기로 수확하는 과정에서 가질 수 있는 최대이익을 구하는 문제이다. 정사각형 모양으로 계속해서 고정적으로 크기를 늘려가며 탐색해야 하기 때문에 브루트포스로 풀어야 한다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
let sum = -Infinity;
const n = +inputs[0];
const trees = inputs.slice(1).map((t) => t.split(" ").map(Number));
 
for (let size = 0; size < n; size++) {
  for (let i = 0; i < n - size; i++) {
    for (let j = i; j < n - size; j++) {
      let temp = 0;
      for (let x = i; x <= i + size; x++) {
        for (let y = j; y <= j + size; y++) {
          temp += trees[x][y];
        }
      }
      sum = Math.max(sum, temp);
    }
  }
}
 
console.log(sum);

하지만 이런 방식으로 브루트포스를 돌게 되면 시간 초과의 결과를 받게 된다. 따라서 미리 사각형 별로 가질 수 있는 이익의 누적값을 따로 기록해놓고 이를 이용하여 계산해야 한다.

const prefixSum = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
 
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    prefixSum[i][j] =
      trees[i - 1][j - 1] +
      prefixSum[i - 1][j] +
      prefixSum[i][j - 1] -
      prefixSum[i - 1][j - 1];
  }
}

해당 이중 for문을 사용해서 미리 가질 수 있는 사각형의 크기만큼의 누적합을 기록한다. 해당 사각형의 경우 무조건 정사각형이 아닌, 0,0부터 시작해서 각 좌표까지의 크기를 가지는 직사각형이다.

for (let size = 1; size <= n; size++) {
  for (let i = size; i <= n; i++) {
    for (let j = size; j <= n; j++) {
      const temp =
        prefixSum[i][j] -
        prefixSum[i - size][j] -
        prefixSum[i][j - size] +
        prefixSum[i - size][j - size];
      sum = Math.max(sum, temp);
    }
  }
}

누적합을 구했으면 정사각형에 맞게 값을 잘라내어 구해야 한다. 각 직사각형의 누적합으로 되어 있으므로 정사각형을 만들 때는 위 옆의 누적합은 빼고 대각선의 누적합을 더하면 해당 정사각형의 누적합을 구할 수 있다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
let sum = -Infinity;
const n = +inputs[0];
const trees = inputs.slice(1).map((t) => t.split(" ").map(Number));
 
const prefixSum = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
 
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    prefixSum[i][j] =
      trees[i - 1][j - 1] +
      prefixSum[i - 1][j] +
      prefixSum[i][j - 1] -
      prefixSum[i - 1][j - 1];
  }
}
 
for (let size = 1; size <= n; size++) {
  for (let i = size; i <= n; i++) {
    for (let j = size; j <= n; j++) {
      const temp =
        prefixSum[i][j] -
        prefixSum[i - size][j] -
        prefixSum[i][j - size] +
        prefixSum[i - size][j - size];
      sum = Math.max(sum, temp);
    }
  }
}
 
console.log(sum);