[백준]1107번 리모컨

 

문제

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

1107번: 리모컨

 

---

문제 풀이

 필자는 해당 문제를 처음에는 수학적으로 접근을 하였다. 하지만 계속되는 예외 케이스들에 걸려 계속 오답처리가 되었다. 6번을 틀리고 나서 문제 풀이 방법을 변경하였다.

역대 최다 시도 달성..

해당 문제의 제시된 조건을 보면 제한 시간이 2초였다. 그래서 브루트포스로 접근해보았다. 최대 목표 채널은 500,000 이므로 최대 자리수를 10의 6승에서 내려가는 것이 최대 크기일 것이다. 

 

 즉 시간 복잡도는 (사용 가능한 버튼 개수)^6으로 그렇게 크지 않아 브루트포스로 진행하였다.

 

해당 문제는 다양한 케이스가 존재하여 코드를 보며 천천히 진행하겠다.

 

 

우선 아래의 코드를 보자

const target = Number(input())
const c = Number(input());
const wrongBtn = c === 0 ? [] : input().split(' ').map(Number);
const btn = [0,1,2,3,4,5,6,7,8,9].filter((v)=>!wrongBtn.includes(v));
let answer = Math.abs(target - 100);

이 코드들은 문제에서 주어지는 입력을 통해 데이터를 정리한 부분이다.

• target : 목표 채널
• c : 고장난 버튼의 개수
• wrongBtn : 고장난 버튼의 배열
• btn : 고장나지 않은 버튼의 배열
• answer : 답이 저장될 변수 (할당을 위와 같이 한 이유는 처음 위치한 채널이 100이기 때문이다)

 

const makeNum = (num, digit) =>{
    if(num.toString().length >= digit){
        const temp = Math.abs(num - target) + digit;
        if(answer > temp){
            answer = temp;
        }
        return;
    }else{
        btn.map((v)=>{
            makeNum( (num*10) + v, digit);
        })
    }
}

위 코드는 사용 가능한 버튼을 이용하여 원하는 숫자를 만드는 함수이다. 원하는 자리의 숫자를 완성하면 누른 버튼의 숫자를 answer과 비교한다.

 > 해당 숫자를 만들면서 누른 버튼의 수 = 해당 숫자의 자리 수 + +,-버튼을 누른 횟수

 

 

btn.filter((v)=> v!==0).map((v)=>{

    for(let a = target.toString().length+1; a >=1;a--){
        makeNum(v,a);
    }
})

위에서 만든 makeNum함수를 적용하는 부분이다. 이 때 모든 자릿수를 확인해보는 것이 완벽하게 구분 가능하므로 target숫자의 자리수부터 1자리까지 진행한다. 이 때 0을 제외한 이유는 0이 맨앞자리로 올 수 없기 때문이다.

 

if(btn.includes(0)){
    const temp = Math.abs(0 - target) + 1;
    if(answer > temp){
        answer = temp;
    }
}

0이 오는 경우는 위와 같이 하나의 if문의로 분기처리해준다.

 

제출 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`500000
8
0 2 3 4 6 7 8 9`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();





const target = Number(input())
const c = Number(input());
const wrongBtn = c === 0 ? [] : input().split(' ').map(Number);
const btn = [0,1,2,3,4,5,6,7,8,9].filter((v)=>!wrongBtn.includes(v));
let answer = Math.abs(target - 100);

const makeNum = (num, digit) =>{
    if(num.toString().length >= digit){
        const temp = Math.abs(num - target) + digit;
        if(answer > temp){
            answer = temp;
        }
        return;
    }else{
        btn.map((v)=>{
            makeNum( (num*10) + v, digit);
        })
    }
}

btn.filter((v)=> v!==0).map((v)=>{

    for(let a = target.toString().length+1; a >=1;a--){
        makeNum(v,a);
    }
})

if(btn.includes(0)){
    const temp = Math.abs(0 - target) + 1;
    if(answer > temp){
        answer = temp;
    }
}


console.log(answer);