브루트 포스

2023. 03. 27.

2798번 (블랙잭)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const numbers = input[1].split(' ').map(Number);
let answer = 0;
let dif = M;
let sum = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (i === j) {
      j++;
    }
    for (let k = 0; k < N; k++) {
      if (k === i || k === j) {
        k++;
      }
      sum = numbers[i] + numbers[j] + numbers[k];
      if (sum > M) {
        sum = 0;
      }
      if (dif > M - sum) {
        dif = M - sum;
        answer = sum;
      }
    }
  }
}

console.log(answer);

브루트 포스 알고리즘이라고 해서 시간복잡도를 아예 신경 쓰지 않았는데 이렇게 해도 되나 싶은 마음이 든다(..)

3중 for문을 돌리고 같은 카드를 중복 선택할 수 없으므로 j를 돌릴 때에는 i와 같으면 스킵하고, k를 돌릴 때에는 i또는 j와 같으면 스킵했다.

sum에 3가지 숫자의 합을 넣고 M에서 sum을 뺀 값이 현재 가장 적은 차이가 나는 dif의 값보다 작으면 dif를 갱신하고 정답에 해당 값을 넣어준다.

3가지 숫자의 합이 M을 넘으면 안되므로 만약 그럴 경우 sum을 0으로 만들어주었다.

2231번 (분해합)

const fs = require("fs");
const input = +fs.readFileSync("./input.txt").toString().trim();
let answer = 0;

for (let i = input; i >= 0; i--) {
  if (i === 0 && answer === 0) {
    answer = 0;
  }
  const length = (i+"").length;
  let sum = i;
  for (let j = 0; j < length; j++) {
    sum += +(i+"")[j];
  }
  if (input === sum) {
    answer = i;
  }
}

console.log(answer);

역시나 브루트 포스 알고리즘이라서 for문을 통해 input부터 0까지 내려가며 탐색하였다.

만약 i 가 0이고 answer가 0이면 (생성자를 찾지 못했다는 뜻) answer를 0으로 하였다.

분해합을 생성하는 과정은 sum에 원본숫자 i를 넣고 i를 string으로 변환하여 각 자리 숫자를 숫자형으로 만들어 더하는 것이다.

만약 input과 sum이 같으면 answer에 i를 대입한다.

7568번 (덩치)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
const N = +input.shift();
let answer = new Array(5);

for (let i = 0; i < input.length; i++) {
  input[i] = input[i].split(" ").map(Number);
}

for (let i = 0; i < N; i++) {
  let rank = 1;
  for (let j = 0; j < N; j++) {
    if (i !== j) {
      if (input[i][0] < input[j][0] && input[i][1] < input[j][1]) {
        rank++;
      }
    }
  }
  answer[i] = rank;
}

console.log(answer.join(" "));

우선 인풋을 비교하기 편하게 이차원 배열 형태로 받아준다.

첫번째 사람부터, 다른 모든 사람과 비교하여 자신보다 덩치가 큰 사람이 있는 경우 rank에 1을 더한다.

이러한 방식으로 하면 문제 출력처럼 겹치는 랭크가 나올 수 있게 된다.

answer의 i번 인덱스에 rank를 넣어준다.

answer를 join을 이용해 문제 출력에 맞게 출력한다.

1436번 (영화감독 숌)

const fs = require("fs");
const input = +fs.readFileSync("./input.txt").toString().trim();

let num = 666;

let i = 1;
while (i !== input) {
  num++;
  if ((num + "").includes("666")) {
    i++;
  }
}

console.log(num);

num은 666, i는 1로 세팅한다.

num을 1씩 증가하며 666을 포함한 숫자가 있으면 i를 증가시킨다.

i가 input과 같아지면 멈추고 num을 출력한다.

1018번 (체스판 다시 칠하기)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
const length = input.shift().split(" ").map(Number);
let answer = 99999999;
let num = 0;
let blackBoardNum = 0;
let whiteBoardNum = 0;
const blackBoard = [
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB"
];
const whiteBoard = [
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW"
]

for (let i = 0; i <= length[0]-8; i++) {
  for (let j = 0; j <= length[1]-8; j++) {
    checkPaintNum(i, j);
  }
}

function checkPaintNum(height, width) {
  blackBoardNum = 0;
  whiteBoardNum = 0;
  for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
      if (blackBoard[i][j] !== input[height+i][width+j]) {
        blackBoardNum++;
      }
      if (whiteBoard[i][j] !== input[height+i][width+j]) {
        whiteBoardNum++;
      }
    }
  }
  blackBoardNum > whiteBoardNum ? num = whiteBoardNum : num = blackBoardNum;
  if (num < answer) {
    answer = num;
  }
}

console.log(answer);

B로 시작하는 보드, W로 시작하는 보드를 배열로 준비했다.

이 보드들과 비교하여 다른 요소가 있으면 숫자를 1 증가시키는 방법으로 칠할 인덱스의 개수를 구한다.

두 숫자 중 더 작은 숫자를 num에 넣고 answer보다 num이 작으면 answer를 업데이트한다.

이 과정을 한칸씩 옮기면서 수행한다.

answer를 출력한다.

2309번 (일곱 난쟁이)

const fs = require('fs');
const input = fs
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split('\n')
  .map(Number);
let sum = 0;
let notDwarf = [];

input.forEach((i) => {
  sum += i;
});

for (let i = 0; i < input.length; i++) {
  for (let j = 0; j < input.length; j++) {
    if (i !== j) {
      if (input[i] + input[j] === sum - 100) {
        notDwarf = [input[i], input[j]];
        break;
      }
    }
  }
}

let answer = input.filter((i) => i !== notDwarf[0] && i !== notDwarf[1]);
answer = answer.sort((a, b) => a - b);

console.log(answer.join('\n'));

9명의 난쟁이들의 키의 합을 구하고 거기서 100을 빼줬다.

2중 for문을 돌려서 두 난쟁이의 키의 합이 해당 값과 같은 것을 찾아냈다.

이렇게 되면 찾아낸 두 난쟁이가 가짜 난쟁이이다.