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

이 문제는 그리디 알고리즘으로 풀었다.

 

일단 완전 탐색은 어림도 없다. 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 이 +, - 각각 존재하므로 버튼의 총 수는 18개가 될 수 있는데, 18^7 만 해도 약 6억번의 연산을 수행해야 하므로 1초가 훌쩍 넘는다.

 

다이나믹 프로그래밍은 메모리 문제가 발생할 수 있고, 숫자의 범위가 커 애초에 잘 겹치지도 않아 시간이 오래 걸린다.

 

이 문제의 핵심은 1의 자리부터 각 자리의 해당 숫자를 보고 올릴지 말지를 판단하는 아이디어로 접근하는 것이다. 가령 16이라면 1의 자리부터 시작하면 6이고, 올렸을 때 4번, 내렸을 때 6번을 통해 해당 자리를 0으로 만들 수 있다. 따라서 올리고, 20이 되었을 때 10의 자리를 보면 2이므로 내린다. 그러면 총 6번의 연산으로 정답을 도출할 수 있다.

 

가장 어려운 부분은 해당 자리가 5일 때인데, 이 때는 다음 자리를 봐야 한다. 2550을 예시로 들었을 때가 가장 헷갈리는데, 10의 자리 입장에서 다음 숫자를 보면 똑같이 5이다. 이 때 올린다면 2600 이 되어 4번, 3번 내리면 0이 되고, 내린다면 2500이 되어 5번, 2번 내려서 0이 되므로 헷갈린다.

이 부분에서 검색을 통해 알고리즘을 확인하였고, 올려서 해결한 코드를 확인하였다. 결론적으로 555와 같은 부분이 연속되는 경우가 헷갈리는 것인데, 올리면 560이 되어 다음에 4번의 연산만을 할 수 있으므로 올리는 것이 정답이라는 얘기였다.

 

정리하면

해당 자릿수가 0 ~ 4면 내리고, 6 ~ 9면 올린다.

5인 경우에는 다음 자릿수를 확인하고, 0 ~ 4면 내리고, 5 ~ 9면 올린다.

로 알고리즘을 짜면 정답이 나온다.

#include <string>
#include <vector>

using namespace std;

int extractDigit(int storey) {
    return storey % 10;
}

int nextDigit(int storey) {
    return ((storey % 100) - extractDigit(storey)) / 10;
}

int solution(int storey) {
    int answer = 0;
    
    while (storey != 0) {
        int digit = extractDigit(storey);
        
        if (0 <= digit && digit <= 4) {
            answer += digit;
            storey -= digit;
        }
        else if (6 <= digit && digit <= 9) {
            int rest = 10 - digit;
            
            answer += rest;
            storey += rest;
        }
        else {
            int next = nextDigit(storey);
            
            if (0 <= next && next <= 4) {
                storey -= 5;
                answer += 5;
            }
            else {
                storey += 5;
                answer += 5;
            }
        }
        
        storey /= 10;
    }
    
    return answer;
}