백준 18230 < 2xN 예쁜 타일링 > JavaScript

📍문제 링크

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

18230번: 2xN 예쁜 타일링

 

📍알고리즘 분류

- 그리디 알고리즘

- 정렬

 

📍문제 풀이

2 * 1 타일과 2 * 2 타일에 점수가 있을 때, 정해진 공간 N에 타일을 깔며 점수 최대값을 획득하는 문제

 

각 타일 배열을 오름차순으로 정렬하여 pop으로 꺼내서 사용 (성능을 위해)

2 * 1 타일 2개의 점수와 2 * 2 타일 1개의 점수를 비교하여 큰 쪽을 사용

N 이 홀수이면, 무조건 2 * 1 타일을 하나 사용해야 하므로 반복문 전에 짝수로 만들어줌

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, A, B] = input[0].split(" ").map(Number);
  const smallTiles = input[1]
    .split(" ")
    .map(Number)
    .sort((a, b) => a - b);
  const bigTiles = input[2]
    .split(" ")
    .map(Number)
    .sort((a, b) => a - b);
  let restArea = N;
  let answer = 0;

  // 홀수이면 2*1타일 무조건 하나 사용
  if (restArea % 2 === 1) {
    answer += smallTiles.pop();
    restArea--;
  }

  // N = 짝수이므로 2개씩 빼기
  while (restArea > 0) {
    const smallLen = smallTiles.length;
    const bigLen = bigTiles.length;

    if (!bigLen) {
      answer += smallTiles.pop() + smallTiles.pop();
    } else if (smallLen < 2) {
      answer += bigTiles.pop();
    } else {
      if (
        bigTiles[bigLen - 1] >
        smallTiles[smallLen - 1] + smallTiles[smallLen - 2]
      ) {
        answer += bigTiles.pop();
      } else {
        answer += smallTiles.pop() + smallTiles.pop();
      }
    }
    restArea -= 2;
  }
  console.log(answer);
});

 

📍리뷰

- DP로도 해결할 수 있을 것 같다