[JS] 백준 1107번 : 리모컨 - 브루투포스, 완전탐색

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

1107번: 리모컨

 

'

풀이방법

1. 가려고하는 채널을 기준으로 하는 것이 아닌 0번 채널 ~ 9999999번 채널을 모두 탐색하면서 답을 찾는 것이다.

2.먼저 100번에서 +,- 만 눌렀을 때의 누른 횟수와

3. 0~9999999번 채널을 눌러가면서 찾은 최소 누른 횟수를 비교한다

0~9999999번 채널 탐색

1. 예를 들어 순회하면서 현재 50번이라는 채널까지 왔다고 가정하자, 그리고 가려고하는 채널은 115번이다.

2. 50번을 리모컨으로 온전히 다 누를 수 있는지 확인한다.

3. 누를 수 있다면 50번의 문자열 길이 값 + 가려고하는 채널 200번까지 +,- 버튼을 누른 횟수 를 구한다.

4. 5, 0 =2번, 115-50= 65번  => 즉 67번을 눌러야 원하는 채널에 도달한다.

5. 이런 식으로 원하는 채널에 도달하기위해 누른 횟수를 저장해가면서 가장 최솟값을 만든다.

6. 이때 누른 횟수가 커질 때가 생기는데 이 때가 누른 횟수의 최솟값을 정하는 타이밍이다.

7. 아래 이미지를 보면서 이해하자

 

내 제출

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

let N = Number(input.shift());
let M = Number(input.shift());
let answer = 0;
let arr = [];
if (M > 0) {
  arr = input.shift().split(" ").map(Number);
}

const check = (num, broken) => {
  //만약 num이 115면
  //1, 1, 5 버튼이 부숴진 버튼에 포함되는지 확인하는 것이다.
  while (true) {
    if (broken.includes(num % 10)) {
      return false;
    } else {
      num = Math.floor(num / 10);
    }
    if (num === 0) {
      break;
    }
  }
  return true;
};

let max = Math.abs(N - 100);
let min = Number.MAX_SAFE_INTEGER;
//0~999999의 숫자들을 순회하면서
//그 채널로 이동하기 위한 버튼 누른 횟수 + 가려고한 채널을 위한 +, -버튼 누른 횟수를 출력해간다.
for (let i = 0; i <= 999999; i++) {
  //순회하는 숫자가 리모컨 버튼으로 온전히 모두 누를 수 있다면
  if (check(i, arr)) {
    //i 채널로 이동하기 위한 버튼 누른 횟수 + 가려고한 채널을 가기위해 +, -버튼 누른 횟수
    let temp = i.toString().length + Math.abs(N - i);

    if (temp < min) {
      min = temp;
    } else if (temp > min) {
      break;
    }
  }
}
answer = Math.min(min, max);
console.log(answer);

 

 

💢어려웠던 점

1. 가려고하는 채널에 기준을 두고 문제를 풀려고 했지만 아니였다.

-브루트포스문제임을 파악하지 못했다.

-브루트포스문제인 만큼 모든 경우의 수를 도출해내는 방식을 이용해야한다.

2. 103번채널의 경우 +,-로 가는게 더 빠른데 이를 해결하는 방법을 생각해내지 못했다.

-미리 가려고하는 채널 - 100을 해서 버튼을 눌러 이동한 값과 비교하면 되는 문제였다.

3. (중요)현재 숫자가 리모컨 버튼으로 온전히 누를 수 있는지 확인하는 함수 check에서 생긴 문제

...


const check = (num, broken) => {
  while (true) {
    if (broken.includes(num % 10)) {
      return false;
    } else {
      num = Math.floor(num / 10);
    }
    if (num === 0) {
      break;
    }
  }
  return true;
};

...

- 정답은 위와 같은 코드이다.

-하지만 아래의 코드처럼 바꾸면 정답이 아니게 된다.

const check = (num, broken) => {
  while (num !== 0) {
    if (broken.includes(num % 10)) {
      return false;
    } else {
      num = Math.floor(num / 10);
    }
  }
  return true;
};

-이유는 만약 0번이 부숴졌을 경우에 num에 0이 들어가는 경우 whil문을 들어가지 않기 때문에 true로 된다,

-즉 0번은 부숴졌는데 0번을 리모컨으로 온전히 누를 수 있다고 판단하기 때문이다.

-그래서 첫 번째 코드처럼 0번이 부숴져있을 때 0번을 누를 수 있는지 확인하고나서 while을 멈춰줘야한다.