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

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

프로그래머스

풀이

주어진 변수 storey의 범위가 100,000,000 이므로 BFS 를 사용해 해결할 수 없는 문제입니다.

 

따라서, Greedy 하게 문제를 해결할 수 있는지를 생각해 보면 됩니다.

 

주어진 storey에 더하거나 뺄 수 있는 수는 절대값이 10^n인 수 입니다. 따라서 주어진 수의 가장 작은 자릿 수부터 0으로 만들어 나가면 문제를 해결할 수 있습니다.

 

16의 경우 가장 작은 자릿수 6을 먼저 0으로 만들어야 합니다. 이때 +4를 할 경우 더 적은 횟수로 0을 만들 수 있습니다. 이후 20이 되면 -20으로 6번만에 0을 만들 수 있습니다.

 

가장 작은 자릿수가 5인 경우에는 다음 자릿수가 5 이상인 경우 올려주면 유리하고, 5 미만인 경우 뺴주어야 유리합니다.

555 (5) -> 560 (4) -> 600 (4) -> 1000 (1) -> 0 (14번) 

555 (5) -> 550 (5) -> 500 (5)  -> 0 (15 번)

 

구현의 경우 현재 자릿 수를 0으로 만든 후는 앞의 남은 자릿수들만 확인하면 되므로 storey /= 10이 됩니다. 

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int storey) {
    int answer = 0;

    while (storey > 0) {
        int digit = storey % 10;
        storey = 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;
}