마법의 엘리베이터

마법의 엘리베이터

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

문제

풀이(DFS)

경우의 수는 2가지가 있다. 올라갈 때, 내려갈 때이다.
예를 들어서 2554를 설명하자면

다음과 같다.
2554에서 마지막 부터 시작한다.
1. 4에서 Down은 4 UP은 6이다.
2. 4에서 Down으로 가면 올림수는 없다. 그래서 5, 5로 나누어진다.
3. 반면에 4에서 UP으로 하게 되면 올림수가 생겨 6, 4로 나누어진다.
이렇게 하여 최소값을 구한다.

생각 못했던 것이 있었는데 마지막 자리수에서 isUp일 때 올림수가 생겨 1을 더 추가해줘야 한다는 것이다. 예를 들어 2554에서 2부분을 isUp하게 되면 10000이 되기 때문에 1을 빼줘야 한다.

def solution(storey):
    
    s = str(storey)
    dp = {}
    def dfs(p, isUp):
        if (p, isUp) in dp:
            return dp[(p, isUp)]
        ## 마지막 자리수에서 isUp이 False이면 올림수없으므로 0리턴
        if p == -1 and not isUp:
            return 0
        ## 마지막 자리수에서 isUp이 True이면 올림수 있으므로 1리턴
        if p == -1 and isUp:
            return 1
        target = int(s[p])
        ## 위층 방향이라면, 올림값이 있으므로 1더해줌
        if isUp:
            target += 1
        ## 위층 방향으로 가기(다음 p에서 1더해줘야함), 아래층 방향으로 가기
        num = min(dfs(p - 1, True) + (10 - target), dfs(p - 1, False) + target)
        dp[(p, isUp)] = num
        return num
    
    return dfs(len(s) - 1, False)

결과