[프로그래머스] Level 2. 마법의 엘리베이터

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

프로그래머스

 

해결방법 (실패)

1. 1의자리수부터 점점 올려가면서 내려가는게 효율적일지, 10층까지 올라간다음 한칸 내려오는게 효율적일지 계산한다. 만약 5보다  작다면 내려가는게 이득이고, 5이상이라면 올라가는게 이득이다. 5라면 5칸 올라간다음 10층을 한번 내려와야 하므로, 5까지는  내려가는게 이득이다.
2. 이 방법으로 모든 자리수를 계산하면 된다...고생각했다

#include <string>
#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    
    while(storey !=0 ){
        int down = storey % 10;
        int up = 11-down; //위로올라갔으니,10층 내려와야함.
        
        answer += down <= up ? down : up-1; //이동해야 하는 층수를  더함.10층내려오는건 다음루프에서 진행.
        if(up<down) storey += 10;
        storey/=10;
    }
    
    return answer;
}

 

그러나 테스트케이스 3개에서 실패했다. 이유를 찾을 수 없어서 반례를 제공받았다.  485층일 경우를 생각해보자

1. 5층을 내려온다. 480층이 된다. => 5
2. 20층을 올라간다. 500층이 된다. => 7
3. 500층을 내려간다. 0층이 된다.도착! =>12

답이 12일것같지만, 사실 더 빠른 길이 있다.

1. 5층을 올라간다. 490층이 된다 =>5
2. 10층을 올라간다. 500층이 된다. =>6
3. 500층을 내려간다. 0층이 된다. =>11

문제가 무엇인가 하니, 5층일때가 문제이다. 5층인데 다음자릿수에서 올라가는게 이득이라면, 어차피 올라갈 길을 미리 올라가는 것이므로 올라가는게 이득이다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    
    while(storey !=0 ){
        int down = storey % 10;
        storey/=10;
        
        if(down <5) answer += down;
        else if(down >5){
            answer += 10-down;
            storey +=1;
        }
        else{
            answer += 5;
            if(storey%10 >= 5) storey +=1; //올라가는걸 택함.
        }
    }
    
    return answer;
}

 

반례 아니었으면 죽을뻔했다!!! 섬세한 손길이 필요한 문제였다