[Programmers] 점프와 순간 이동

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12980

해설

점프 : K칸 앞으로 점프, K만큼 건전지 사용

순간 이동: (현재까지 온 거리)*2의 위치로 이동, 건전지 사용 안함

0의 위치에서 n으로 이동할 때, 점프 or 순간 이동을 사용하는데 건전지 사용량을 최소로 사용해야한다. 이때 최소 건전지 사용량을 return 해라.

건전지를 최소로 사용하기 위해서는 점프를 최소로하고 순간이동을 최대로 늘려야한다. 문제의 주어진 예시를 통해 살펴보자. 순간 이동을 최대로 하기 위해서는 마지막 n으로 오기 직전일때 2배를 했을 때 가장 이동 구간이 크기 때문에 마지막에는 최대한 순간이동을 사용하는 것이 좋다. 그러나 점프는 앞으로만 이동이 가능하므로 (직전 위치)*2가 n이 되면 좋지만 n보다 크면 안된다. 그러므로 n이 짝수였다면 마지막 이동은 순간이동이고, 홀수였다면 마지막 이동에는 한 칸 점프(최소 점프)하고 바로 직전이 순간이동이였으면 된다. 이 과정을 처음위치 0으로 돌아갈때 까지 역으로 살펴보면 최소 점프, 최대 순간이동의 횟수를 구할 수 있고, 그렇다면 이때 최소 점프를 통해 최소 건전지사용량을 구할 수 있다. 문제의 입출력 예시 n이 5000일 때를 살펴보면 다음과 같다.

5000은 짝수이기 때문에 바로 직전에 5000을 2로 나눈 몫인 2500(2500*2=5000)에서 왔어야 한다. 다시 2500으로 최소 건전지를 사용해서 왔으려면 순간이동을 많이 해야하는데 2500은 짝수이므로 1250(1250*2=2500)에서 왔어야한다. 다시 1250은 위와 같은 과정에 의해서 625에서 왔어야한다. 한편 625는 홀수 이므로 625까지 이동하기 위해서 직전에는 순간이동으로 올 수 없다. 그러므로 점프를 사용했어야 하는데 최소 점프라면 한 칸 직전인 624에서 점프해서 왔을 것이다. 그리고 다시 624는 짝수이므로 312에서 왔을 것이고, 312는 156에서 왔고, 156은 78에서 왔다. 78은 39에서 왔고, 39는 38에서 한 칸 점프로 왔다. 다시 38은 19에서 왔고, 19은 18에서 한 칸 점프로 왔다. 18은 9에서 9는 8에서 점프로 왔고다. 8은 4에서 4는 2에서 순간이동으로 왔다. 그리고 2는 1에서 순간이동(1*2=2)이고 1은 0에서 한칸 점프로 왔다. 여기서 점프를 한 곳을 구하면 0에서 1, 8에서 9, 18에서 19, 38에서 39로, 624에서 615로 이동할 때이다. 총 5번 이동할때 모두 한 칸씩 점프를 사용해서 건전지 사용량은 5이다.

위 과정을 알고리즘으로 나타내면 다음과 같다.

그리고 수직선 상에서 0은 기준이고 n은 0부터 도착지까지의 거리이다. 수직선의 개념을 살펴보면 n을 기준으로 보고 0을 도착점으로 생각해도 무방하다. 즉, 0에서 n으로 이동이 아니라 n에서 0으로 이동으로 생각할 때 최초 시작 위치(current)는 n이다.

1. current가 짝수라면 다음 위치(직전 위치)는 current를 2로 나눈 몫이다. 홀수라면 다음 위치(직전 위치)는 1을 뺀 값이다.

2. 다시 현재 위치를 위에서 구한 값으로 갱신한다.

3. 위 과정을 n이 0이 될때 까지 반복한다.

코드

def solution(n):
    answer = 0

    while n>0:
        if n % 2 == 0:
            n //= 2
        else:
            answer += 1
            n -= 1

    return answer