[백준/G4] 10836 여왕벌

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

시간복잡도

최종코드 : O(N**2)

풀이

단순 구현 문제가 아니라… 문제를 먼저 쉽게 푸는 방법을 생각해야 했던 문제였다.

1. 더할 성장값들을 배열에 전부 한번에 저장하고
2. 조건 상 결국 0번째 열을 제외하고 각 열의 최상단 행의 값(=최상단 위치에 들어갈 성장값)이 해당 열에 전부 들어가야한다.

단순 구현으로는 15점까지는 쉽게 풀리지만 문제에서 제시하는 입력범위와 제한조건에 맞추려면 구현능력보다 문제를 풀어갈 수 있는 아이디어가 중요한 문제

15점 코드

function growOnBorder(M, arr, values) {
  let startX = M - 1;
  let startY = 0;
  let idx = 0;

  while (idx < values.length) {
    arr[startX][startY] += values[idx];

    let nx = startX - 1;
    let ny = startY;

    if (nx < 0) {
      nx = startX;
      ny = startY + 1;
    }
    startX = nx;
    startY = ny;
    idx++;
  }

  for (let i = 1; i < M; i++) {
    for (let j = 1; j < M; j++) {
      arr[i][j] = arr[0][j]
    }
  }
  return arr;
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./10836.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N] = input[0].split(" ").map(Number);

let arr = Array(M)
  .fill(0)
  .map(() => Array(M).fill(1));

for (let i = 1; i < N + 1; i++) {
  let [zero, one, two] = input[i].split(" ").map(Number);

  let temp = Array(zero + one + two);
  let idx = 0;

  for (let j = 0; j < zero; j++) {
    temp[idx++] = 0;
  }

  for (let j = 0; j < one; j++) {
    temp[idx++] = 1;
  }

  for (let j = 0; j < two; j++) {
    temp[idx++] = 2;
  }

  // 성장
  arr = growOnBorder(M, arr, temp);
}

for (const row of arr) {
  console.log(row.join(" "));
}

말그대로 문제에 적힌대로 그대로 구현했다

83점 코드

function growOnBorder(M, arr, values) {
  let startX = M - 1;
  let startY = 0;
  let idx = 0;

  while (idx < values.length) {
    arr[startX][startY] += values[idx];

    let nx = startX - 1;
    let ny = startY;

    if (nx < 0) {
      nx = startX;
      ny = startY + 1;
    }
    startX = nx;
    startY = ny;
    idx++;
  }

  return arr;
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./10836.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N] = input[0].split(" ").map(Number);

let arr = Array(M)
  .fill(0)
  .map(() => Array(M).fill(1));

for (let i = 1; i < N + 1; i++) {
  let [zero, one, two] = input[i].split(" ").map(Number);

  let temp = Array(zero + one + two);
  let idx = 0;

  for (let j = 0; j < zero; j++) {
    temp[idx++] = 0;
  }

  for (let j = 0; j < one; j++) {
    temp[idx++] = 1;
  }

  for (let j = 0; j < two; j++) {
    temp[idx++] = 2;
  }

  // 성장
  arr = growOnBorder(M, arr, temp);
}

let initialValues = arr[0].slice(1)
for (const row of arr) {
	let ans = [row[0], ...initialValues]
	console.log(ans.join(" "))
}

처음 변경되는 경계의 벌의 성장만 업데이트하고 그다음 나머지를 채우니 83점이 나왔다

최종코드(100점 코드)

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./10836.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N] = input[0].split(" ").map(Number);
// 성장할 값
let values = Array(2 * M - 1).fill(0);

for (let i = 1; i <= N; i++) {
  let [zero, one, two] = input[i].split(" ").map(Number);
  let idx = 0;

  // 0만큼 더하는건의미가 없으므로 idx만 변화
  idx += zero;

  for (let j = 0; j < one; j++) {
    values[idx++] += 1;
  }

  for (let j = 0; j < two; j++) {
    values[idx++] += 2;
  }
}

for (let i = M - 1; i >= 0; i--) {
  // 왼쪽열 채워넣으면서
  let row = [];
  row.push(values[i] + 1);
  for (let j = M; j < 2 * M - 1; j++) {
    // 나머지 열도 채워넣어 row완성 (나머지열은 최상단 행의 value와 같음)
    row.push(values[j] + 1);
  }
  console.log(row.join(" "));
}

성장 배열을 받아두고 이중for문 한번만에 배열을 완성하니 100점으로 통과됨

136092kb 5468ms