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

 처음 문제를 읽고 바로 BFS구나! 싶어서 bfs로 코딩했다. 얼마 전 워딩이 거의 비슷한 문제를 만났어서 더욱 그랬다(아래 첨부) 그러나 시간초과에 틀렸습니다가 무더기로 나왔다. 잘 읽어보니

저 위의 100까지의 숫자 외에도 1000 10000까지도 나갈 수 있는 것이었다. 그래서 주어진 숫자의 자릿수까지만 bfs 할 수 있도록 했는데도 38점 밖에 받지 못했다. 

너무도 당연하게 bfs가 맞다고 생각하고 있어서 내 코드가 어디가 잘못된 건지 갈피를 못잡고 있었다. 이 풀이가 잘못된건가? 라고 생각했을 땐 이미 늦었다. 이것과 비슷한 문제를 풀어본적이 있는데도 풀이를 바로 떠올리지 못한 것이 참 아쉽다. 아직까지도 시간복잡도 계산을 잘 못하는 것이 컸다. 시간복잡도를 통해 bfs가 불가함을 바로 알아챘어야했다.

 

결론적으로 이 문제는 그리디 알고리즘이다. 잘하면 DP로도 풀 수 있을 것 같다. 10의 제곱으로 주어지는게 힌트였다. 예를 들어 2001 이라는 숫자가 들어오면 마지막 1의 자릿수 때문에 방법이 달라진다. 즉 1의 자리를 내릴것이냐 올릴것이냐, 2000으로 만들것이냐 2010으로 만들것이냐를 정하는 것이 핵심이다. 그리고 문제는 5일때 인데, 내려야할지 올려야할지 알 수 없다. 

이건 5를 만났을 때 무조건 올리는 부분과 내리는 부분을 둘다 계산해 더 낮은 숫자를 리턴하도록 했다.

 

유사한 문제 https://tigerfrom2.tistory.com/13

프로그래머스 - 점프와 순간이동 (C++)

 

https://tigerfrom2.tistory.com/62

백준 5014번 스타트링크 (C++)

 

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

int solution(int storey) {
    int answer = 0;
    int answer2 = 0;
    int init = storey;
    while(storey != 0){
        int tmp = storey % 10;
        if(tmp <= 5 ){ // 무조건 내림
            answer += tmp;
            storey = storey / 10;
        }
        else if(tmp > 5){ // 무조건 올림
            answer += (10 - tmp);
            storey = storey / 10 + 1;
        }
    }
    
    storey = init;
    while(storey != 0){
        int tmp = storey % 10;
        if(tmp < 5 ){ // 무조건 내림
            answer2 += tmp;
            storey = storey / 10;
        }
        else if(tmp >= 5){ // 무조건 올림
            answer2 += (10 - tmp);
            storey = storey / 10 + 1;
        }
    }
    if(answer > answer2)  return answer2;
    else return answer;
}