백준 - 02

2798번 - 븍랙잭 (브루트 포스)

• 입력 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

  합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

  5 21
  5 6 7 8 9
  

• 출력 첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

  21;
  

---

solution

직관적으로 3중 반복문으로 풀 수 있습니다.

주의할 점

• 동일한 카드 선택 X
• 뽑는 순서 상관 X

let input = require("fs")
  .readFileSync("dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((x) => x.split(" ").map(Number));

let [n, m] = input[0];
let arr = input[1];

let diff = m;
let sum = 0;
let answer = 0;

for (let i = 0; i < n - 2; i++)
  for (let j = i + 1; j < n - 1; j++)
    for (let k = j + 1; k < n; k++) {
      if (diff == 0) break;

      sum = arr[i] + arr[j] + arr[k];

      if (sum <= m && m - sum < diff) {
        diff = m - sum;
        answer = sum;
      }
    }

console.log(answer);

• 재귀 함수를 활용한 조합을 구현해서 풀어볼 예정입니다.

---

1018번 - 체스판 다시 칠하기 (브루트 포스)

• 입력 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.

  둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

  8 8
  WBWBWBWB
  BWBWBWBW
  WBWBWBWB
  BWBBBWBW
  WBWBWBWB
  BWBWBWBW
  WBWBWBWB
  BWBWBWBW
  

• 출력 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

  1
  

---

solution

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

let [N, M] = input.shift().split(" ").map(Number);

// 기준이 될 체스판 정의
let white = [
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
];
let black = [
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
];

// 비교할 8 x 8 체스판의 좌상단 좌표를 받습니다
const paintWhite = (x, y) => {
  let count = 0;

  for (let i = y; i < y + 8; i++) {
    for (let j = x; j < x + 8; j++) {
      // 받은 좌표부터 8 x 8 체스판들을 완전 탐색합니다.
      if (input[i][j] !== white[i - y][j - x]) {
        count++;
      }
    }
  }

  return count;
};

const paintBlack = (x, y) => {
  let count = 0;

  for (let i = y; i < y + 8; i++) {
    for (let j = x; j < x + 8; j++) {
      if (input[i][j] !== black[i - y][j - x]) {
        count++;
      }
    }
  }

  return count;
};

let answer = [];

// 8 x 8 체스판은 가로(N - 7) X 세로(M - 7)개
for (let i = 0; i < N - 7; i++) {
  for (let j = 0; j < M - 7; j++) {
    answer.push(paintWhite(j, i));
    answer.push(paintBlack(j, i));
  }
}

console.log(Math.min(...answer));