[lv2] 마법의 엘리베이터

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

 

매번 탐색마다 첫번 째 자리수 (storey % 10 값)만 비교하면 되므로 그리디로 접근하려다가, 올라가는 경우 다음 층에 영향을 주기에 일단락 했다.

 

문제에서

storey <= 10억(2^9) 이므로,

올라간다/내려간다  이진 탐색으로 구현하면 O(2^9)로 끝낼 수 있다.

 

class Solution {
    int answer = Integer.MAX_VALUE;

    void solve(int storey, int cnt) {
        if(storey < 10) {
            // 한 자리 수 층에서 올라가는 경우와 내려가는 경우 비교
            answer = Math.min(answer, cnt + Math.min(10 - storey + 1, storey));
            return;
        }

        // 올라가는 경우
        solve(storey / 10 + 1, cnt + 10 - (storey % 10));

        // 내려가는 경우
        solve(storey / 10, cnt + (storey % 10));
    }
    public int solution(int storey) {

        solve(storey, 0);

        return answer;
    }
}