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

풀이 방법

그래프 탐색보단 storey를 0으로 만드는 방법을 찾으면 된다.

(1) 일의 자리가 4이하라면 - 연산으로 빼버리는게 최소의 연산으로 0에 가깝게 만들 수 있고.

(2) 일의 자리가 6이상이라면 + 연산으로 10을 만들어 -10 연산을 하는게 최소의 연산이 된다.

    EX) 6이라면 6에서 + 연산으로 10을 만들고 -10 연산을하면 5번의 연산이 필요하다.

           그러나 6에서 - 연산으로 0을 만들자면 -1 연산을 6번이 필요하다.

           즉 6이상이면 +연산을 해버리는게 최소의 연산이다.

 

(3) 일의 자리가 5라면

5를 0으로 만드나, 5를 10으로 만드나 5번의 연산이 똑같이 필요한데

다음 자리 수를 보고 더 이득이 되는 방향을 잡을 수 있다.

 

다음 자리 수가 5~9면 일의 자리수를 올림해버리는게 연산을 최소화할 수 있다.

다음 자리 수가 0~4면 일의 자리수를 - 연산으로 지워버리는게 연산을 최소화 할 수 있다.

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int storey) {
    int answer = 0;
    
    while(storey!=0) { // storey가 0이 될때까지
        if(storey%10<5) { // 일의 자리수가 5미만이라면 -로 빼버리는게 이득.
            answer+=storey%10; // 일의 자리수 크기만큼 -1 연산이 필요.
        } else if (storey%10==5) { // 일의 자리수가 5라면
            if((storey/10)%10>=5) // 다음 자리수가 5이상이라면
                storey+=10; // 덧셈 연산으로 +5 해버리는게 (올림) 이득
            answer+=5; // 덧셈 5번 연산 필요
        } else {
            answer+=10-(storey%10); // 일의 자리수가 6이상이라면 올림 - 10을 만들기 위한 연산횟수 필요
            storey+=10; // 올림에 의해 십의 자리에 1을 더해줌
        }
        storey/=10; // 일의 자리 제거
    }
    
    return answer;
}