[프로그래머스/Lv2] 점프와 순간 이동

문제

한 번에 K칸을 앞으로 점프하거나,

(현재까지 온 거리) x 2 에 해당하는 위치로 순간이동할 수 있는 기능을 가진 아이언 슈트가 있다.

 

이 아이언 슈트는 건전지로 작동하는데, 순간이동을 하면 건전지가 줄어들지 않지만 앞으로 K만큼 점프하면 K만큼 건전지 사용량이 든다.

 

이 아이언 슈트를 착용하고 N 만큼 떨어져 있는 장소로 가려고 할 때 건전지 사용량을 최소로 이동하려고 한다.

아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. 숫자 N : 1 이상 10억 이하의 자연수

2. 숫자 K : 1 이상의 자연수

 

 

코드

def solution(n):
    answer = 1
    while n != 1:
        if n % 2 == 1:
            answer += 1
            n = int((n-1)/ 2)
        else:
            n = int(n / 2)
    
    return answer

 

 

설명

아이언 슈트의 순간이동 기능을 사용하려면 적어도 한 칸은 이동해야 한다.

따라서 0칸->1칸 으로 점프는 항상 이루어 진다.

 

아이언 슈트로 N칸까지 건전지를 최소한으로 사용하는 방법을 역으로 생각해본다.

N을 2로 나눠서 나머지가 0이라면 그 칸은 순간이동으로 이동할 수 있는 칸이다.

나머지가 1이라면 그 칸은 이전 수에서 점프가 필요한 칸이라고 생각할 수 있다.

 

위 과정을 N을 2로 나눠 N이 1이 될 때 까지 반복한다.

이것들을 코드로 구현한다.

 

 

answer = 1

0칸->1칸으로 점프는 항상 이루어지기 때문에 계산하지 않는다.

 

while n != 1:

n이 1이 될 때까지 반복한다.

 

if n % 2 == 1:
	answer += 1
	n = int((n-1)/ 2)

n을 2로 나눴을 때 나머지가 1이라면 answer에 1을 더하고

n을 1뺀뒤 2로 나눈 수를 다시 n에 저장한다.

 

else:
	n = int(n / 2)

나머지가 0이라면 n을 2로 나눈 수를 다시 n에 저장한다.

 

return answer

반복이 끝난 answer를 반환한다.