프로그래머스 - 마법의 엘리베이터

문제

현재 층수 \(L(1 \le L \le 100,000,000)\)과 절댓값이 \(10^{c}(c\ge 0, c \in \mathbb{N})\)인 엘리베이터 버튼이 주어질 때, 0층으로 갈 수 있는 경우의 수 중 버튼을 가장 적게 누르는 경우를 찾아야 한다.
음수 층으로는 갈 수 없다.

풀이

• 6층의 경우 1, 1, 1, 1, -10 순서로 누르는 경우가 최적의 경우이다.
  하지만 76층의 경우 1, 1, 1, 1, 10, 10, -100 순서로 누르는 경우가 최적의 경우이다.
  이처럼 숫자의 올림을 처리하는 것이 다음 자릿수의 값에 따라 변하기 때문에, 1의 자리부터 가장 왼쪽 자리 순서로 해결해야 한다.
• [1, 4]의 경우, -1을 누르는 것이 최적이다.
• [6, 9]의 경우, 1을 누르는 것이 최적이다.
• 5는 +1, -1을 누르는 경우가 모두 같기 때문에 아래와 같이 경우를 나눈다.
• 현재 1의 자리가 5일 경우, 연속되는 5의 개수(cnt5)를 센다.
  • 5가 아닌 첫 자리수가 6 이상인 경우, 1을 누르는 것이 최적이다.
    • 655의 경우, -1x5, -10x5, 100x4, -1000 -> 15인데, 1x5, 10x4, 100x3, -1000 -> 13이다.
  • 5가 아닌 첫 자리수가 4 이하인 경우, -1을 누르는 것이 최적이다.
    • 355의 경우, -1x5, -10x5, -100x3 -> 13인데, 1x5, 10x4, -400x5 -> 14이다.
  • cnt5는 2 이하인 경우 5*cnt5, 3 이상인 경우 5*2+4*(cnt5-2)로 계산한다.
    • 5 : -1x5
    • 55 : -1x5, -10x5
    • 555 : 1x5, 10x4, (100x4, -1000x1)
    • 5555 : 1x5, 10x4, 100x4, (1000x4, -10000x1)
  • 0으로 만든 이후에는 10으로 나누어, 코드의 가독성을 높일 수 있다.

소스코드

using namespace std;

int solution(int storey) {
    int ans=0;
    while(storey>0){
        while(storey>0 && storey%10==0) storey/=10;
        if(storey%10==5){
            int cnt5=0, tn=storey;
            while(tn%10==5){
                tn/=10;
                cnt5++;
            }
            if(tn==0){
                if(cnt5<3) ans+=cnt5*5;
                else ans+=10+4*(cnt5-2);
            }
            else if(tn%10>5){
                ans+=5+(cnt5-1)*4+(10-tn%10);
            }
            else{
                ans+=5*cnt5+tn%10;
            }
            storey=tn;
        }
        else if(storey%10>5){
            ans+=10-(storey%10);
            storey+=10-storey%10;
        }
        else{
            ans+=storey%10;
        }
        storey/=10;
    }
    return ans;
}

풀고나서