프로그래머스 [Lv. 2] 마법의 엘리베이터 {언어 : Python} [백트래킹]

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

프로그래머스

정답 코드

answer = 72
def solution(storey):
    def dfs(s, tot):
        global answer
        if answer <= tot:
            return
        if s == 0:
            answer = tot
            return
        divide = 10 ** (len(str(s)) - 1)
        cnt = abs(s // divide)
        tmp = cnt * divide
        tmp3 = 10 * divide
        dfs(s-tmp, tot+cnt)
        dfs(tmp3-s, tot+1)

    dfs(storey, 0)
    return answer

풀이 방법

1. answer를 72로 둔 이유는 최악의 수가 99_999_999를 전부 9번씩 눌러서 9 * 8 = 72번 버튼을 누르는 것이다.
2. 경우의 수는 2개로 봤다.
   1. 현재 가장 큰 자리수의 개수 만큼 누르기
      1. 987인 경우 => 987 - 900 = 87
   2. 10 ** 현재 자릿수에서 현재 값을 빼기
      1. 987인 경우 => 1000 - 987 = 13
3. 현재 버튼을 누른 횟수가 answer보다 크거나 같은 경우는 재귀를 이어가지 않고 종료한다.
4. 이후 최종 answer를 반환하면 끝!

느낀점

• 더 좋은 방법이 있지만 떠오르지 않았고 재귀를 사용했다.
• 결국 답을 찾는 문제에 다양한 풀이가 있다는 것을 새삼 깨달았다.
• 중간에 가지치기를 했다는 점에서 백트래킹에 가까워 보인다.
• 다른 풀이는 아래와 같다.

https://sound-programming.tistory.com/202

프로그래머스 [Lv. 2] 마법의 엘리베이터 {언어 : JavaScript} [다시 풀어 보기]