[Programmers] 마법의 엘리베이터

특정 층수가 주어지면 0층까지의 최단 거리를 찾는 문제이다.
조건이 있다면 한 번에 이동할 수 있는 층수는 절댓값이 10의 n승인 수이다. ex) -1, 10, 100, 10000

처음 접근은 끝에있는 자리수부터 케이스를 나누어서 5이상인 경우, 이하인 경우 등으로 나누어, Greedy로 접근해보려 했는데, 특정 테스트케이스를 통과하지 못했다.

너무 경우의 수가 복잡하게 나눠지는 느낌이 들어서 그냥 재귀를 이용한 DFS로 해결하였다.

#include <string>
#include <vector>

using namespace std;
int answer = 100000000;
int f(int num, int stone){
        
    if(num<10){
       stone+=min(num, 11-num);
       answer = min(answer,stone);
       return 0;
    }
    
    
    int l = num%10;
    num/=10;
    if(num>0) f(num +1, stone+10-l);                  
    f(num , stone+l);
    
    return 0;
}
int solution(int storey) {
    
    f(storey, 0);
    return answer;
}

나는 현재 사용한 돌 갯수와, 현재 층수를 매개변수로 넘겼는데, 다른 사람 풀이를 보니 return 값을 이용하여 최솟값을 업데이트 하고 비교하는 방식이 있었는데 더 깔끔했다. (매개변수로 층수만 넘겨서)

내가 처음 접근한 것처럼 푼 코드도 있었다. 차분히 생각했다면 되게 케이스가 깔끔하게 나눠지는 문제였다.