프로그래머스 코딩테스트 연습 - 마법의 엘리베이터 JavaScript

function solution(storey) {
    let answer = parseInt(storey);
    const counting = (num, count) => {
        console.log(num, count);
        if(num < 10) {
            if(answer > count + num) {
                answer = count + num;
            }
            if(answer > count + 10 - num + 1) {
                answer = count + 10 - num + 1; // 10으로 만든 뒤 -10
            }
            return;
        }
        const down = parseInt(num % 10);
        counting(parseInt(num / 10) + 1, count + 10 - down); // 자리 수 올림
        counting(parseInt(num / 10), count + down); // 자리 수 내림
    }
    counting(answer, 0);
    return answer;
}

10^n 단위 숫자를 빼고 더하여 초기에 주어진 숫자를 0으로 만드는 문제이다.

요점은, 덧셈이나 뺄셈 횟수가 최소가 되어야 한다는 점 이었다.

3일 때는 3번 빼는 게 빠르지만, 9일때는 1을 더한뒤 10을 빼는게 더 빠른 점을 고려해야했다.

dfs방식으로 문제를 접근하여, 모든 경우의 수를 따지는 방식을 사용하였다.

지금 생각해보니, dfs 함수 내부에서 중간에 이미 계산 횟수가 지금까지 계산한 최소값보다 커지면, return하는 방식으로 최적화가 가능할 것 같다.