[JS][백준]1107_리모컨

문제 번호

1107번: 리모컨

 

 

 

알고리즘 분류

• 브루트포스 알고리즘

 

 

문제 풀이

 채널의 범위가 왜 무제한까지 있는지와 몇 가지 경우만 잘 생각한다면 브루트포스 알고리즘을 사용해서 쉽게 풀 수 있다.

 

 N의 범위는 최대 500,000 이지만 채널의 범위는 무제한이다. 이는 500,000보다 큰 채널에서 500,000 채널로 올 수 있다는 뜻이다. 이점을 놓치면 탐색하는 채널의 범위를 500,000으로 제한하는 실수를 할 수 있다. 시작 채널이 100이므로 500,000 -100 = 499900이다. 500,000 + 499,900 = 999,900인데 이보다 큰 채널은 100번 채널에서 +- 버튼만 사용해서 이동할 때보다 무조건 많은 횟수의 버튼을 눌러야 하기 때문에 살펴볼 필요가 없다.

for(let i=0; i<=999900; i++)

 

 이제 숫자 버튼을 눌러서 이동할 수 있는 채널중 N번 채널에 가장 가까운 채널로 이동한 뒤, +- 버튼을 사용해서 N번 채널에 도달할 것이다.

 숫자버튼을 눌러서 이동할 수 있는 채널 중에 N번 채널에 100번 채널보다 가까이 있는 채널이 있는지 확인해보자.

(N까지의 거리가 i번 채널이 가깝냐 100번 채널이 가깝냐를 살펴보는 것)

  for(let i=0; i<=999900; i++) {
    let check = true;
    let cur = i.toString();
    for(let j=0; j<cur.length; j++) { // 이동할 수 있는 숫자인가?
      if(!nums[cur[j]]){
        check = false;
        break;
      }
    }

 

 만약 숫자 버튼을 눌러서 이동할 수 있는 채널 중에 N번 채널에 더 가까운 채널이 있다면 실제로 해당 채널로 이동해서 N번 채널로 도착하려면 몇 회의 버튼을 눌러야 하는지 계산해보자.

if(check) {
      cur = Number(cur);
      let newDist = Math.abs(N-cur);
      if(newDist < dist) {  // 100번에서 가는거보다 cur 에서 가는게 더 빠르다.    // 거리가 멀지만 더 적게 눌러서 이동할 수 있는 경우가 있나? 자릿수가 바뀔때?
        // 실제로 cur로 이동해서 얼마나 걸리는 계산한다.
        let temp = 0;
        temp += cur.toString().length; // 숫자 버튼 누르는 횟수.
        temp += Math.abs(N - cur);  // +- 버튼 누르는 횟수.
        if(temp < min){  // 실제로 버튼을 누르는 횟수가 더 적다.
          dist = Math.abs(N - cur);          
          min = temp;
        }
      }
    }

 

 실제로 버튼을 누르는 횟수가 더 적다면 dist( N번 채널까지의 거리)와 min(실제로 버튼을 누르는 횟수)를 업데이트시켜준다.

 

전체 코드. closest 변수는 실제로 사용되지는 않았다.

/**
 * N 으로가자. 0<=N<=500000
 * 현재 100번.
 * N과 가장 가까운 채널에서 +- 로 이동하는게 젤 빠르다.
 * 채널은 무한대로 있기때문에 500000보다 큰 채널에서 내려올 수 있다.
 * 100번에서 500000로 가는데 + 로 499900 번 누르면된다.
 * 500000 + 499900 까지가 최대범위일듯. 이 범위를 넘어가면 100번에서 +를 눌러서 가는게 더 빠르다.
 * 대략 10^6. 숫자버튼10개. => 10^7. 
 * i번 채널이 고장나지 않은 버튼을 눌러서 이동 할 수 있는지 알아본다.
 * 이동할 수 있는 채널중 N번과 가장 가까운 채널로 이동한다.
 */

function main() {
  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const N = +input[0].trim();
  const M = +input[1].trim();
  let broken = [];
  if (M !== 0)
    broken = input.slice(2)[0].split(' ').map(_ => Number(_.trim()));

  let nums = new Array(10).fill(true);
  for (let i = 0; i < broken.length; i++) { // 고장난 버튼을 표기한다.
    nums[broken[i]] = false;
  }
  return console.log(sol(N, M, nums));
}
function sol(N, M, nums) {
  if(N == 100) return 0;

  let closest = 100;  // N번과 최인접한 채널.
  let dist = Math.abs(N-100); // N번 채널과의 차이.
  let min = dist; // 버튼을 누르는 횟수다.

  for(let i=0; i<=999900; i++) {
    let check = true;
    let cur = i.toString();
    for(let j=0; j<cur.length; j++) { // 이동할 수 있는 숫자인가?
      if(!nums[cur[j]]){
        check = false;
        break;
      }
    }

    if(check) {
      cur = Number(cur);
      let newDist = Math.abs(N-cur);
      if(newDist < dist) {  // 100번에서 가는거보다 cur 에서 가는게 더 빠르다.    // 거리가 멀지만 더 적게 눌러서 이동할 수 있는 경우가 있나? 자릿수가 바뀔때?
        // 실제로 cur로 이동해서 얼마나 걸리는 계산한다.
        let temp = 0;
        temp += cur.toString().length; // 숫자 버튼 누르는 횟수.
        temp += Math.abs(N - cur);  // +- 버튼 누르는 횟수.
        if(temp < min){  // 실제로 버튼을 누르는 횟수가 더 적다.
          dist = Math.abs(N - cur);          
          min = temp;
        }
      }
    }
  }
  return min;
}
main();

 

특이사항

 거리가 가깝다 하더라도 실제로 버튼을 누르는 횟수를 비교해 봤을 때 100번 채널에서 '+-버튼'을 사용하여 이동하는 것이 더 빠른 경우가 있었다. 첫 풀이에 해당 경우를 놓쳐서 당황했었는데 침착하게 다시 살펴본 결과 그리 어렵지 않은 문제라는 걸 알 수 있었다.