[LV2] 마법의 엘리베이터

문제 설명

마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다.

마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다.

단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.
마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.

예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.

마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다.

민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 1 ≤ storey ≤ 100,000,000

입출력 예

storey	result
16	6
2554	16

 

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• -1, +100이 적힌 버튼을 4번, +10이 적힌 버튼을 5번, -1000이 적힌 버튼을 3번 누르면 0층에 도착 할 수 있습니다. 그러므로 16을 return 합니다.

 

쉽게 말해, 주어진 숫자에서 ±n을 해서 최소한의 연산으로 0을 만들라는 문제였다.

이렇게만 보면 단순한 그리디 문제로 보여 처음에는 

1. 일의 자리 수가 5보다 작으면 -n, 크거나 같으면 +n을 한다.
2. 마지막 자리 수가 0이기 때문에, answer에 각 자릿수의 모든 수를 더한다

위의 과정을 거쳐 문제를 풀었으나 당연히 개같이 실패.

 

실패 사유는 반례가 너무 많았다는 것인데,,.,.

예를 들어보자면, 2994라는 수에 위 코드를 적용한다면, 24라는 답이 나오게 된다.

storey	2994	2990	2900	2000	0
answer	0	4	13	22	24

 

하지만 문제에서 제시한 최적의 조건을 따라가기 위해서는

 

storey	2994	3000	0
answer	0	6	9

 

단 6번의 연산만으로 답을 구할 수 있다. 

5보다 작다고 무조건 아래로, 5보다 크거나 같다고 위로 가는 것이 답이 아니라는 것이다.

 

그렇다면, 어떤 층에서 위, 아래로 가는 모든 경우의 수를 따져 비교해 봐야 한다.

모든 경우의 수를 비교하기 위해 DFS를 사용하기로 했다.

1. 현재 층에서 위로 올라가는 경우와 아래로 내려가는 경우를 모두 실행
2. 각각 10 - 1의 자리 수와 1의 자리 수를 총 이동 횟수에 추가
3. 현재 층이 10으로 나누어진다면, 나누어지지 않을 때 까지 10으로 나눈다
4. 다시 위/아래로 이동
5. 현재 층수가 0인 경우, 현재까지의 총 이동 횟수를 answer에 넣어준다
6. answer의 최솟값을 리턴

우선 dfs의 매개변수로는 현재 층과 총 이동횟수만 있어도 충분할 것 같다.

종료 조건을 설정해 주고, 위/아래 이동과 10으로 나누는 코드를 작성해준다

 

const dfs = (storey, sum) => {
	//종료 조건
	if(storey === 0){
    	ans.push(sum)
        return
    }
    //마지막 자리수
    const lastNum = storey % 10
    //마지막 자리수가 0 = 10으로 나눠진다면
    if(lastNum === 0){
        //10으로 나눈 수를 넣고 진행
        dfs(storey / 10, sum)
    } else {
        //아닌 경우, 각각 위, 아래로 이동한 뒤 dfs 진행
        dfs(storey + (10-lastNum), sum + (10-lastNum))
        dfs(storey - lastNum, sum + lastNum)
    }
}

 

dfs 함수에 문제에서 주어진 storey와 0을 넣고 실행해보면,..,,

 

 

Maximum Call Stack 에러가 난다.

이 말인 즉슨, 종료 조건이 제대로 설정되지 않아 무한 루프가 일어난다는 뜻.

어디서 문제가 발생했는지 찾기 위해 콘솔에 코드를 찍어보았다.

 

무한 루프의 원인

 

현재 층이 1층일 때, 로직에 의하면

1층	+9	10	/10	1
	-1	0	-	-

 

1층 -> 10층 -> 1층 -> 10층....이 계속 반복되어 무한 루프가 발생하는 것이었다.

때문에, 1층일 때의 종료 조건을 따로 설정해 무한 루프를 막아줘야 했다.

 

const dfs = (storey, sum) => {
	//종료 조건
    if(storey < 2){
        //1층일 경우 => 1 -> 0 / 1 -> 10
        //10층에서는 다시 10으로 나눌 경우 1이 됨 => 무한루프
        if(storey === 1){
            //1층일 경우 누적합+1(0으로 만듬)을 넣음
            ans.push(sum + 1)
        } else {
            //0층일 경우 누적 합을 넣음
            ans.push(sum)
        }
        return
    }
    //마지막 자리수
    const lastNum = storey % 10
    //마지막 자리수가 0 = 10으로 나눠진다면
    if(lastNum === 0){
        //10으로 나눈 수를 넣고 진행
        dfs(storey / 10, sum)
    } else {
        //아닌 경우, 각각 위, 아래로 이동한 뒤 dfs 진행
        dfs(storey + (10-lastNum), sum + (10-lastNum))
        dfs(storey - lastNum, sum + lastNum)
    }
}

 

개비스콘

 

최종 코드는 다음과 같다

 

function solution(storey) {
    let ans = []
    const dfs = (storey, sum) => {
        //종료 조건 -> 무한 반복 피함
        if(storey < 2){
            //1층일 경우 => 1 -> 0 / 1 -> 10
            //10층에서는 다시 10으로 나눌 경우 1이 됨 => 무한루프
           if(storey === 1){
               //1층일 경우 누적합+1(0으로 만듬)을 넣음
                ans.push(sum+1)
            } else {
                //0층일 경우 누적 합을 넣음
                ans.push(sum)
            }
            return
        }
        //마지막 자리수
        const lastNum = storey % 10
        //마지막 자리수가 0 = 10으로 나눠짐
        if(lastNum === 0){
            //10으로 나눈 수를 넣고 진행
            dfs(storey / 10, sum)
        } else {
            //아닌 경우, 각각 위, 아래로 이동한 뒤 dfs 진행
            dfs(storey + (10-lastNum), sum + (10-lastNum))
            dfs(storey - lastNum, sum + lastNum)
        }
    }
    dfs(storey, 0)
    //이동 횟수의 최솟값을 리턴
    return Math.min(...ans)
}