마법의 엘리베이터

문제 설명

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

---

문제 해설

 

문제의 조건을 살펴보자. 엘리베이터의 가장 효율적인 이동경로를 설정하라는 문제이다.

 

엘리베이터는 10의 N승만큼 움직일 수 있음으로, 가장 최소의 이동경로를 설정하려면 고려해야할 점이 다음과 같다.

 

• 현재 이동할 수 있는거리가 위로짧은가? 아래로짧은가?
• 현재 이동할 수 있는거리가 위, 아래가 동일할 때 다음노드에 자릿수를 넘길 때 더 짧게 이동이 가능한가?

 

위 아래로 이동하는 경우의 수는 매우 간단하게, 10에 빼버리면 나타낼 수 있다.

 

더 크면 더 작으면 위 또는 아래로 이동시키면 되기 때문이다.

(10 - 6 이면, 위로가면서 다음으로 넘기면 해당 노드에서 이동하게되는 총 이동거리는 5 임으로 효율적이다.)

 

그러나, 현재 노드를 다음노드에 넘겼을 때 다음노드가 더 효율적으로 이동이 가능한지를 고려해야 한다.

(10 - 5 에 위 아래의 이동거리가 5로 동일하고, 다음 노드가 5 이상일 경우 이동하면 무조건 효율적이다. 어차피 다음노드도 다음노드로  값을 1 넘기면서 이동하기 때문)

 

 

현재 아래 이동거리와 위 이동거리가 동일할 때

다음노드로 1을 넘기는, 위로 이동을 선택할 경우

이동거리가 1 늘어나기 때문에 5일때 무조건 넘기면 손해다.

---

첫 번째 시도

#include <string>
#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    string number = to_string(storey);
    for (int i = 0; i < number.size(); i++)
    {
        if (number[i] - '0' > 5)
            answer += (10 - (number[i] - '0')) + 1;
        else
            answer += number[i] - '0';
    }

    return answer;
}

실패

 

그냥 단순하게 5 이상일 때 값을 넘겨버리도록 설정했다.

그러나 코드 자체도 오류가 있어서 실패. if문의 true일경우의 행동사항을 잘못작성했다.

---

두 번째 시도

 

#include <string>
#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    int Next = 0;
    string number = to_string(storey);
    for (auto def = number.rbegin(); def != number.rend(); def++)
    {
        int nownumber = *def - '0';
        if (Next == 1) nownumber++;

        if (nownumber > 5) {
            Next = 1;
            answer += 10 - nownumber;
        }
        else {
            Next = 0;
            answer += nownumber;
        }
    }
    
    answer += Next;
    return answer;
}

실패

 

이번에는 좀 더 값처리를 직관적으로 바꾸었다.

넘어가는 숫자를 카운팅해서 넘어갔을 때를 확인하고, 값을 더해주게 하였다.

 

마지막 값이 10이 되었을 경우 값이 넘어가게 되기때문에 마지막에 Next를 더해주어서 10의 결과값의 오차범위를 수정한다.

 

그러나, 이렇게 해놓았을 경우, 485 입력값을 넣었을 때 11이 나와야하나, 12가 나와서 실패한다.

 

현재 노드가 5 일때 넘기거나 넘기지 않음을 결정하지 못한다. 다음값이 8일경우 무조건 넘겨야 이득이다.

넘기지 않았을 때의 값은 5, 2(8에서 2만큼 이동하고 넘김) , 5 의 이동거리를 나타냄으로 12이다.

넘겼을 때의 값은 5, 1(뒷 숫자에서 1이 넘어와서 9에서 1만큼 이동), 5 의 이동거리를 나타냄으로 11이다.

 

위 계산을 고려해서 다시 작성해야한다.

---

세 번째 시도

#include <string>
#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    int Next = 0;
    string numbers = to_string(storey);
     for (auto def = numbers.rbegin(); def != numbers.rend()-1; def++)
    {
        int nownumber = *def - '0';
        int nextnumber = *(def + 1) - '0';
        if (Next == 1) nownumber++;

        if ((nownumber >= 5 && nextnumber > 4)) {
            Next = 1;
            answer += 10 - nownumber;
        }
        else if (nownumber > 5)
        {
            Next = 1;
            answer += 10 - nownumber;
        }
        else {
            Next = 0;
            answer += nownumber;
        }
    }
    int last = numbers[0] - '0' + Next;
    answer += last > 5 ? 11 - last : last;
    return answer;
}

성공

 

현재 값이 5이상일 때, 다음값이 4보다 클 경우 넘겨주고, 5보다 크면 무조건 넘기게, 아닐경우 현재값을 내려버리게 처리하면 모든 객체에 효율적인 이동방식이 이루어진다.

 

다음 노드를 반영해서 데이터를 처리하고.

 

마지막 노드는 5보다 크면 위로 이동하고 1만큼 더 이동하는게 효율적이고, 적으면 그대로 내려버리는게 효율적이다.

그럼으로 따로 계산공식을 넣어서 처리한다.