프로그래머스 Level2 마법의 엘리베이터 (Java)

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

문제

• 엘리베이터는 10의 제곱단위로 움직인다.
• 엘리베이터의 최소층은 0이다.
• 최소층 보다 밑으로 내려갈 수 없다.
• 현재 층에서 0층으로 가는 최소횟수을 구하시오.
• 예를들어 현재 16층에 있다면 두가지 방법이 있다.
  • -1을 6번, -10을 1번 움직여 총 7번움직이는 방법
  • +1을 4번, -10을 2번 움직여 총 6번움직이는 방법 -> 최소횟수

제한사항

• 1 ≤ storey ≤ 100,000,000

코드

class Solution {
    private static int answer = Integer.MAX_VALUE;
    private static String str;
    private static void DFS(int depth,int offset,int count) {
        if(depth == -1) {
            answer = Math.min(answer, count+offset);
            return;
        }

        int num = str.charAt(depth)-'0'+offset;
        DFS(depth-1,0,count+num);
        DFS(depth-1,1,count+10-num);
    }
    public int solution(int storey) {
        str = Integer.toString(storey);
        DFS(str.length()-1,0,0);
        return answer;
    }
}

풀이

• storey의 크기가 매우 크지만, 10의 제곱단위로 움직이기 때문에 최대 9자리를 탐색하는 것이다. 따라서 완전탐색으로 풀 수 있다.
• 위로 움직일 경우 다음 자리수에서 +1이 된다는 것을 생각해야 한다.
  • 예를들어 16층에서 위로가면 20층으로 다음에는 2번, 16층에서 아래로 가면 다음에는 1번으로 차이가 생긴다.