[programmers] Lv2 마법의 엘리베이터 - Python

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

프로그래머스

 

 

 

<문제 풀이>

- 입력받은 층 수를 각 자릿수로 분리하고 1의 자릿수를 가리키는 idx로 초기화한다.

- 0층으로 내려가기 위해 돌의 개수를 최소로 소모하기 위해서는 해당 자리의 수가 어디에 위치해 있는지에 따라 아래로 내려갈 것인지 위로 올라갈 것인지 판단한다.

- 가리키는 idx가 0 ~ 4인 경우는 내려가는 것이 돌의 소모가 적고 6~9인 경우는 올라가는 것이 돌의 소모가 적다.

- 5에서는 경우의 수가 나누어지는데 입력받은 층이 5로 구성된 층일 때(ex: 5, 55, 555 )와 2 자릿수 이상인 경우이다.

- 전자의 경우에는 내려가는 것이 돌의 소모가 적지만, 후자의 경우 올라갔다가 한 번에 내려가는 것이 돌의 소모가 더 적기 때문이다.

- 첫 번째 code는 내가 푼 풀이 방식이며, 두 번째 code는 같이 스터디하는 분 중 한 분이 푸신 dfs를 이용한 간단한 풀이이다.

 

 

 

<Code>

def solution(storey):
    answer = 0
    storey = list(map(int, str(storey)))    # 숫자를 각 자리수로 나누어 체크 하기 위한 리스트
    now = len(storey) - 1    # 1의 자리가 되는 지점의 idx

    while now >= 0:
        if storey[now] <= 4:    # 해당 자리의 수가 0 ~ 4인 경우 엘리베이터는 내려가는 것이 돌 소모가 적다
            answer += storey[now]    # 내려간 만큼 answer에 사용한 돌의 개수 추가

        elif 6 <= storey[now]:    # 해당 자리의 수가 6 ~ 9인 경우 올라가는 것이 돌 소모가 적다.
            answer += 10 - storey[now]    # 올라간 만큼 answer에 사용한 돌의 개수 추가

            if now == 0:    # 엘리베이터가 올라갔지만 입력받은 값에서 올림이 필요한 경우
                answer += 1    # +1
            else:    # 아닌 경우 다음 idx의 값에 엘리베이터가 올라갔으므로 해당 층의 자리의 수 +1
                storey[now-1] += 1

        else:    # 해당 자리의 수가 5인 경우
            flag = True
            temp = now    # temp는 now의 다음 자리수를 체크하기위한 임시값
            # 입력값의 길이가 2이상인 조건을 추가한 이유는 5로만 구성된 층수일 때, 5층에서는 내려가는 것이 빠르지만
            # 입력받은 층수가 2자리수 이상인  경우에는 올라갔다가 한번에 내려가는 것이 돌 소모가 적기 때문이다.
            while temp >= 0 and len(storey) >= 2:
                # 5와 다른 수가 나온다면 반복문을 빠져나간다.
                if storey[temp] <= 4:
                    flag = False    # 4이하인 경우에는 내려가는 것이 좋다.
                    break
                elif 6 <= storey[temp]:
                    break

                temp -= 1    # 자리수 이동

            if flag:    # 5 다음으로 오는 수가 6이상인 경우
                storey[now-1] += 1    # 엘리베이터가 올라가기 때문에 다음 자리수의 값 +1

            answer += 5    # 사용 돌 개수 추가

        now -= 1    # 다음 자리의 값을 체크하기 위해 idx 이동

    return answer

def solution(storey):
	answer = 200000000
    
    def dfs(x, cnt):
        nonlocal answer
        if x == 0:                                 # 0층으로 이동했다면
            if answer > cnt:                       # answer을 최소값으로 갱신
                answer = cnt
            return

        if x == 1:                                 # 아래의 else문은 1을 10으로 만들고 다시 1을 넣어 재귀하여 
            dfs(0, cnt + 1)                        # 무한 반복이 되므로 1의 경우 따로 분리
        else:                                      # 현재 수의 1의 자리를 0으로 만드는 2가지 방법으로 재귀
            dfs(x // 10, cnt + x % 10)             # 1의 자리 숫자를 빼주는 방법
            dfs(x // 10 + 1, cnt + 10 - x % 10)    # 1의 자리 숫자가 10이 되도록 더해주는 방법
    
    dfs(storey, 0)
    
    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.