[프로그래머스 Lv.2] 마법의 엘리베이터

[문제]

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

프로그래머스

 

[풀이]

 

10^n 단위로 움직일 수 있는 엘리베이터로, 최소한의 경우의 수를 찾아야하는 문제이다. 크게 세 가지 조건만 활용하면 문제를 쉽게 풀 수 있다.

 

1. 현재 자릿수가 6 이상인 경우

: 가장 가까운 10으로 올린다. 이때 앞자리가 변경되기 때문에 올림 처리를 실시해야한다.

 

2. 현재 자릿수가 4 이하인 경우

: 가장 가까운 0으로 내린다

 

3. 현재 자릿수가 5인 경우

: 여기서 올릴지 말지를 고려해야한다. 다음 자릿수가 4 이하라면, 그냥 내려도 된다. 하지만 다음 자릿수가 5 이상이라면, 올리는 것이 더 유리할 "가능성"이 존재한다. 입력값으로 2555가 들어왔다고 생각해보자.

 

- 1의 자리 5

 > 5를 올리면 10, 내리면 0이 되지만, 앞자리수들의 변동이 발생한다.

 > 내리는 경우에는 전부 내리는데, 이러면 

   : 1의 자리 5 : 5번

   : 10의 자리 5 : 5번

   : 100의 자리 5 : 5번

   : 1000의 자리 2 : 2번

   : 총 17번 이동

 

 > 올리는 경우는 전부 올리는데, 이려면

   : 1의 자리 5 : 5번

   : 10의 자리 6(5+1) : 4번

   : 100의 자리 6(5+1) : 4번

   : 1000의 자리 2 : 3번

   : 총 16번 이동

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void Carry(vector<int>& Arr, int index)
{
    int i = index;
    Arr[i] = 0;
    while (true)
    {
        if (i + 1 >= Arr.size())
        {
            Arr.push_back(1); // 자릿수 늘림
            break;
        }
        Arr[i + 1] += 1;

        if (Arr[i + 1] < 10)
        {
            break;
        }

        Arr[i + 1] = 0;
        ++i;
    }
}

int solution(int storey) 
{
    int answer = 0;
    vector<int> Arr;
    int Buffer = storey;
    while (Buffer != 0)
    {
        Arr.push_back(Buffer % 10);
        Buffer /= 10;
    }

    for (int i = 0; i < Arr.size(); i++)
    {
        int CurDigit = Arr[i];
        if (CurDigit >= 6)
        {
            answer += (10 - CurDigit);
            if (i < Arr.size() - 1)
            {
                Arr[i + 1] += 1;
                if (Arr[i + 1] == 10)
                {
                    Carry(Arr, i + 1);
                }
            }
            else
            {
                Arr.push_back(1); // 마지막 자릿수에서 올라가는 경우
            }
        }
        else if (CurDigit == 5) // 앞자리가 6 이상으로 바뀌면 올림, 아니면 내림
        {
            if (i + 1 < Arr.size() && Arr[i + 1] >= 5)
            {
                answer += (10 - CurDigit);
                Arr[i + 1] += 1;
                if (Arr[i + 1] == 10)
                {
                    Carry(Arr, i + 1);
                }
            }
            else
            {
                answer += CurDigit;
            }
        }
        else // 4 <= Temp
        {
            // 4는 그냥 내림
            answer += CurDigit;
        }
    }

    return answer;
}