마법의 엘리베이터

그리디 알고리즘

예시인 2554를 보면

1. 2554는 1의 자리가 4니까 2550으로 만들고 answer += 4 수행해 255로 마무리
2. 255는 1의 자리가 5인데, 10의 자리가 5 이상이니까, 255로 만들고 answer += (10 - 5) 수행해 26으로 마무리
3. 26은 1의 자리가 6이니까 30으로 만들고 answer += (10 - 6)수행해 3으로 마무리
4. 3은 1의 자리가 3이니까 0으로 만들고 answer += 3 수행해 0으로 마무리
5. while (storey > 0) 조건 불만족 하므로 반복 종료

import java.util.*;

class Solution {
    public int solution(int storey) {
        int answer = 0;
        
        //DP문제? 그리디 알고리즘?
        //0보다 작을수는 없지만 storey보다는 얼마든지 커도 됨...
        
        //16에서 10을 가는 방법?
        //16 -> 15 -> 14 -> 13 -> 12 -> 11 -> 10
        //16 -> 17 -> 18 -> 19 -> 20 -> 10
        
        //15에서 10을 가는 방법
        //15 -> 14 -> 13 -> 12 -> 11 -> 10
        //15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 10
    
        //14에서 10을 가는 방법
        //14 -> 13 -> 12 -> 11 -> 10
        //14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 10
        
        //6, 7, 8, 9면 +1하고,
        //1, 2, 3, 4, 5면 -1하고,
        
        int mod, next;
        
        while (storey > 0) {
            mod = storey % 10;//1의 자릿수 파악
            next = (storey / 10) % 10; //10의 자릿수 파악
            System.out.println("mod : " + mod + " next : " + next);

            if (mod > 5 || (mod == 5 && next >= 5)) {// 1의 자릿수가 6, 7, 8, 9이거나, (5면서 다음 자릿수가 5 이상이면)
                answer += (10 - mod); 
                storey += (10 - mod); 
            } else { //1의 자릿수가 0, 1, 2, 3, 4, 5면
                answer += mod; 
            }
            System.out.println("storey : " + storey + " answer : " + answer);

            storey /= 10;
        }
        
        return answer;
    }
}