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

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

프로그래머스

 

🐭 풀이

처음엔 자릿수를 다 더해주면 된다고 생각했습니다.
하지만 문제에 나온 예제 1번 16을 보면,
자릿수를 다 더해주면 7이지만
+1을 4번 누르고, -10을 2번 누르면 총 6번만에 0층에 도달할 수 있습니다.

 

이 예제에서 문제 풀이에 대한 힌트를 얻을 수 있습니다.

 

자릿수를 다 더해주는 경우는
먼저 -1을 6번 눌러서 1의 자리를 없애주고
-10을 1번 눌러서 0으로 만드는 과정입니다.

 

하지만 6번만에 0층에 도달할 수 있는 풀이에서는 매번 현재 상태에서 선택할 수 있는 최선의 방법을 선택합니다.
일의 자리 숫자 6을 보고, 6번을 빼는 것이 아니라 4번을 더하는 탐욕적인 방법을 선택했습니다.
그러면 다음 자릿수는 2가 됩니다.
2는 0이 되려면 2가 필요하고, 10이 되려면 8이 필요하니, 0을 선택합니다.

 

즉 정리하면,
자릿수가 6~9인 경우는 10으로 만들어주고
0-4인 경우는 0으로 만들어주면 됩니다.

 

🚨 5인 경우는 신경을 써야 합니다.
내가 0 또는 10을 선택했을 때 바로 뒤에 일어날 상황을 고려해줘야 합니다.

 

5인 경우 10이 되도록 만들어서 앞 자릿수를 1 늘려주는 경우
555 -> 560 -> 600 -> 1000 -> 0 : 14번

5인 경우 0이 되도록 만들어서 앞 자릿수를 1 줄여주는 경우
555 -> 550 -> 500 -> 0 : 총 15번

555라는 예제에서는 앞 자릿수를 1 늘려주는 것이 좋습니다.
왜냐면 5의 다음 자릿수가 6이 됩니다.
다음 선택에서 6은 0이 되기 위해서는 6가 필요하고, 10이 되기 위해서는 4가 필요하므로, 10이 되기를 선택할 수 있습니다.
더 탐욕적인 선택을 할 수 있도록 도와준 것입니다. ^ㅇ^

 

정리하면 앞 자리수가 5이상인 경우에는 올려주는 것이 유리하고,
반대로 5 미만인 경우에는 0에 더 가까워질 수 있도록 내려주는 것이 유리하겠습니다.

🐭 코드

class Solution {
    public int solution(int storey) {
        int answer = 0;

        while (storey > 0) {
            int digit = storey % 10;
            storey /= 10;

            // 5인 경우, 앞자리 숫자가 5이상이면 올려주는 것이 유리함.
            if (digit == 5) {
                if (storey%10 >= 5) {
                    answer += (10 - digit);
                    storey++;
                }
                else {
                    answer += digit;    
                }
            }
            // 더하는 것이 이득
            else if (digit > 5) {
                answer += (10 - digit);
                storey++;
            }
            // 빼는 것이 이득
            else {
                answer += digit;
            }

        }
        return answer;
    }
}