[알고리즘] 프로그래머스 Lv2 마법의 엘리베이터

문제

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

엘리베이터가 10의 c 제곱에 해당하는 만큼의 층을 움직이는 버튼 밖에 없다. (c>=0)
최소한의 버튼 사용으로 현재 층(storey)에서 0층까지 움직이도록 하고 이때 필요한 버튼 클릭 횟수 구해라

풀이과정

<생각의 흐름>
DFS로 -1, 1, -10, 10, -100, 100... 숫자들을 넣고 주어진 층에 해당하는 수가 나올 때까지 구하는 방식으로 짜볼까?
아냐아냐 자릿수만 생각해도 되는거 아닌가?
오?! 자릿수?! 그리고 재귀?!

라고 생각하며 코드가 생각보다 금방 작성되었다.

1번, 3번, 12번 테스트 케이스에서 오류가 났다.
도저히 반례가 생각나지 않았다...
질문하기를 보았다(이거 그만 봐야하는데ㅜㅜ 실제 코테에서는 못 보잖아... 그만둬..!)

유레카..
반례는 95였다!!!!!

95가 잘 계산되도록, 7이 아니라 6이 나오도록! 코드를 수정했더니 통과되었다.

코드

처음 코드(1, 3, 12번 실패)

def solution(storey):
    if storey < 10:
        if storey <= 5:
            return storey
        else:
            return 10 - storey + 1

    if storey % 10 <= 5:
        return storey % 10 + solution(storey//10)
    else:
        return 10 - (storey % 10) + solution(storey//10)

수정한 코드(통과)

def solution(storey):
    if storey < 10:
        if storey <= 5:
            return storey
        else:
            return 10 - storey + 1

    if storey % 10 <= 5:
        cnt = storey % 10
        storey = round(storey/10) # 여기서 반올림 해주는게 포인트
        return cnt + solution(storey)
    else:
        cnt = 10 - storey % 10
        storey = round(storey/10)
        return cnt + solution(storey)

가장 뒤의 숫자는 따로 cnt로 계산해두고(5보다 클 때, 작을 때 조건 나눠서),
반올림을 하는 것이 포인트이다.

다른 사람의 풀이

def solution(storey):
    if storey < 10 :
        return min(storey, 11 - storey)
    left = storey % 10
    return min(left + solution(storey // 10), 10 - left + solution(storey // 10 + 1))

짧고 강력하다...!
min 내장함수와 재귀를 사용해서 깔끔하게 풀이했다.
오늘도 감탄하며 마무리...