[프로그래머스 / 파이썬] 마법의 엘리베이터

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

프로그래머스

---

문제 해석

엘레베이터가 존재하고, 민수는 주어진 storey층에 있다.

엘레베이터는 +1, -1, +10, -10, +100, -100, ... 10^c 단위로 움직일 수 있다.

엘레베이터는 지하의 층으로 갈 수 없다.

이때 가장 최소로 움직이도록 하는 값을 구하는 문제이다.

---

문제 풀이

문제를 보고 딱 떠오른 방법은 그리디하게 푸는 방법이였다.

1의 자리의 수부터 확인해 나가며 1에서 10이 되는 경우의 수와 0이 되는 경우의 수 두가지로 나눌 수 있었다.

이때 10이 되는 경우의 수는 다음 자리의 수가 +1 되어야 하기 때문에 5의 경우라면 0으로 가도록 구현했다.

-> 실패

예를 들어 85의 상황이라면 85, 80, 0으로 총 13번 이동하여 최소가 되지만,

95의 경우 95, 90, 00으로 총 14번 이동한다. 하지만 최소는 95, 100, 0 으로 6번 이동하는 경우이다.

 

따라서 이를 해결하기 위해 dfs를 통해 완전 탐색을 해주었다.

주어진 최대값이 100,000,000 이기 때문에 2^9로 매우 널널했다.

10과 0이 가까운 경우는 해당 경우로 이동하고, 5로 두 값이 같을 경우만 모두 탐색해주어 문제를 해결했다.

 

---

문제 코드

def solution(storey):
    # 2가지 경우
    # 위로 올라가거나 밑으로 내려가거나
    # 올라갈 때는 다음 자릿수를 +1 해주어야 함.
    answer = []
    
    def dfs(st, count):
        if st == 0:
            answer.append(count)
            return
        
        one = st % 10
        up, down = 10 - one, one
        # up 이나 down 둘 중 더 적게 움직이는 쪽으로 이동
        if up < down:
            dfs(st // 10 + 1, count + up)
        elif down < up:
            dfs(st //10, count + down)
        else:
            # 같다면 둘다 이동해보기
            for i in range(2):
                dfs(st // 10 + i, count + up)
    
    dfs(storey, 0)
    return min(answer)

 

---