문제

• https://school.programmers.co.kr/learn/courses/30/lessons/148653

코드

// dfs
function solution(storey) {
    const ans = [];
    
    const newStorey = storey.toString().split('').map(Number);
    
    function dfs(i, sum, arr) {
        if(arr[i] === 10) {
            // if(i === 0) {
            //     newArr.splice(i, 1, 1, 0);
            //     i++;
            // }
            if(i === 0) ans.push(sum+1)
            else {
                const newArr = [...arr];
                newArr[i-1] += 1;
                dfs(i-1, sum, newArr);
            }
            return;
        }
        
        if(i !== 0) {
            dfs(i-1, sum+arr[i], arr);
            const newArr = [...arr];
            newArr[i-1] += 1;
            dfs(i-1, sum+(10-arr[i]), newArr);
        }
        else {
            ans.push(sum+arr[0]);
            ans.push(sum+(11-arr[0]))
        }
    }
    
    dfs(newStorey.length-1, 0, newStorey)
    
    return Math.min(...ans)
}

DFS

• DFS나 BFS 뭐로 풀든 상관 없다. 하지만 난 DFS가 더 편해서 이거로 풀었다.
• 모든 경우의 수를 계산해서 최솟값을 return 하면 된다.
• dfs 함수에 현재 index(i)와 지금까지의 총합(sum)과 변화한 배열(arr)을 보내준다.

if(arr[i] === 10)

• arr[i]가 10이라는 것은 이전 index에서 1을 올려줘 9가 10이 된 경우다.
• 이 경우 10을 한 번에 계산할 수 없다.
• i가 0일 땐 어차피 10을 한 번에 끝낼 수 있으니 ans.push(sum+1)을 해준다.
• i가 0이 아닐 땐 arr이 계속 변하니까 newArr을 만들어 i-1의 값을 변경해주고, newArr을 넘겨준다.

if(i !== 0)

• arr[i] !== 10 이고 i가 0이 아닐 때, 현재 자리를 0으로 만드는 dfs를 보내준다.
• newArr을 만들어 현재 자리를 10으로 만들어주고(i-1을 +1 해주고) dfs로 newArr을 넘긴다.

if(i === 0)

• 맨 앞자리가 0으로 변할 때와 10으로 변할 때의 값을 모두 ans에 push 해준다.