문제
코드
function solution(storey) {
const ans = [];
const newStorey = storey.toString().split('').map(Number);
function dfs(i, sum, arr) {
if(arr[i] === 10) {
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 해준다.