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

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

프로그래머스

 

#include <string>
using namespace std;

int solution(int storey) {
    int answer = 0;
    while(storey>0)
    {
        int im = storey%10;
        storey/=10;
        int next = storey%10;
        if(im>5||(im==5 && next >= 5))
        {
            storey++;
            answer+=(10-im);
        }
        else
            answer+=im;
    }
    return answer;
}

이 문제는 10의 c제곱에 해당하는 버튼들이 엘리베이터에 있다. 이 때, 현재 층수에서 버튼누르는 수를 최소한으로 하여 0층으로 가고싶다. 이 때, 최소한은 몇번인지를 구하는 문제이다. 

 

문제를 잘보니 올림과 내림을 이용하면 쉽게 해결되겠다는 생각이 들었다. 

따라서 while문을 통해서 제일 작은 자릿수부터 보고 올림과 내림을 정하고 올림이면 다음수에 +1을 한다. 

 

ex) 16 이면 

처음에 im은 6이 된다. 6은 5보다 크니 올림 즉, 10을 만드는게 비용이 적게든다. 근데 올림을 하면 20이 돼야하기 때문에 

10을 나눈 storey에 대해서 +1을 해준다. 

다음은 im이 2가 된다. 2는 내림하는게 비용이 적게 드니 내림을 한다. 다음 storey는 0이므로 종료한다. 그리고 답은 6이 된다. 

 

이 방법에 문제가 한가지 있다면, im이 5일 때이다. 이 때의 최선은 올림이 아니다. 왜냐면 올림, 내림 둘다 비용이 5이기 때문이다. 따라서 이 때의 최선은 그 다음 자릿수에 달려있다. 즉 다음 자릿수가 내림을 해야하는 숫자면 굳이 지금 올림을 해서 비용 1을 추가할 필요가 없다. 

 

#include <string>
using namespace std;

int solution(int storey) {
    int answer = 0;
    while(storey>0)
    {
        int im = storey%10;
        storey/=10;
        int next = storey%10;
        if(im>5||(im==5 && next >= 5))
        {
            storey++;
            answer+=(10-im);
        }
        else
            answer+=im;
    }
    return answer;
}

코드는 아주 간단하다. 

먼저 반복문에서 im을 구하고 그 다음 자릿수인 next까지 구해준다. 

im이 5보다 큰지 아닌지에 따라서 올림 내림을 결정하되 5인 경우에는 그 다음 자릿수가 5보다 큰지 확인하여 결정한다. 

 

이 문제는 그리디 알고리즘을 사용하여 풀었는데 현재 im에 대해서 최선의 선택을 하여 최적의 해를 도출하는 알고리즘을 사용하였다.