[Programmers] 마법의 엘리베이터(LV.2)

풀이 소요시간 : 60분 초과(실패)

보자마자 당연히 BFS 접근을 확신했고, 시간초과로 인한 실패를 맛보았다.

정확성 테스트에서 단 하나의 케이스를 통과하지 못했으니, 어쩌면 운이 없었는지도..
추후 풀이과정을 참고한 결과 그리디한 접근이 정석이였다.

전체코드(BFS) - 시간 초과

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

int storey;
int Visit[100000001];
queue<pair<int, int>> Q;


int Move[18] = { 
    1, -1,
    10, -10,
    100, -100,
    1000, -1000,
    10000, -10000,
    100000, -100000,
    1000000, -1000000,
    10000000, -10000000,
    100000000, -100000000
};

int Bfs() {
    
    while(!Q.empty()) {
        
        int px = Q.front().first;
        int ptime = Q.front().second;
        Q.pop();
        
        if(px == 0) {
            return ptime;
        }   
        
        for(int i = 0; i < 18; i++) {
            int nx = px + Move[i];
            if(nx < 0 || nx > 100000000 || Visit[nx]) continue;    
            Visit[nx] = 1;
            Q.push({nx, ptime + 1});
        }
        
    }
    
    return 0;
}


int solution(int storey) {
    Q.push({storey, 0});
    Visit[storey] = 1;
    return Bfs();
}

전체코드(그리디) - 성공

해당 문제의 그리디한 접근방식은 분명 이후에 사용될 것이라고 생각된다. 앞으로 이 접근방식을 흡수하여 특정 수치 값을 가진 문자열 혹은 수가 주어지고, 이를 줄이거나 늘려나가서 특정 값으로
만드는 유형의 문제의 그리디한 접근방식으로 사용해야겠다.

일의 자리 6 이상

• 올림, 10으로 나누기 진행

일의 자리 4 이하

• 내림, 10으로 나누기 진행

일의 자리 5

• 십의 자리 5 이상 : 올림, 10으로 나누기 진행
• 십의 자리 4 이하 : 내림, 10으로 나누기 진행

10으로 나누기를 반복하다가 0이되면 진행을 멈추고, 사용된 돌의 갯수를 반환한다.

#include<iostream>
using namespace std;


int Magic_Stone(int storey) {
    
    int Total_Stone = 0; 
    while(storey != 0) {
        
        int Last = (storey % 10); 
        
        if(Last >= 6) {                
            Total_Stone += (10 - Last); 
            storey /= 10;               
            storey++;                  
            continue;
        }        
        else if(Last <= 4) {           
            Total_Stone += (Last);      
            storey /= 10;              
            continue;
        }
        else {
            
            Total_Stone += (Last);          
            if(storey > 10) {                
                
                int Head = (storey/10) % 10;  
                if(Head >= 5) {
                    storey /= 10;
                    storey++;
                    continue;
                }
                else {
                    storey /= 10;
                    continue;
                }
                
            } 
            else {                    
                storey -= (Last);
                storey /= 10;
                continue;
            }
            
        }

    }
    
    return Total_Stone;
    
}


int solution(int storey) {
    return Magic_Stone(storey);
}