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

문제

출처

제한

• 주어지지 않음

입력

• 아이언 슈트 구매자가 이동하려는 거리 N
  • 1 <= N <= 10억 (자연수)

출력

• 사용해야 하는 건전지 사용량의 최솟값

규칙

1. K칸 점프
   • 1 <= K (자연수)
   • K만큼 건전지 사용
2. 현재까지 거리 * 2 위치로 순간이동
   • 건전지 사용 X

재구성

입력

• 만들어야 할 수 N

출력

• 0에서 N을 만드는 여러 방법 중, “더하는 수의 총합”이 최소가 되도록 하는 방법에서의 더하는 수의 총합

규칙

1. +K
   • cost: K
2. *2
   • cost: 0

접근

규칙 2에서 힌트를 얻을 수 있는데, 곱하기 2는 이진법에서 shift 연산이다. 따라서 앞으로 수를 이진법으로 다룰 것이다.

+K는 +1과 *2 연산을 사용하여 쪼갤 수 있다.

예를 들어,

K의 일의 자리수가 0이면
K = K' * 2

K의 일의 자리수가 0 또는 1이면
K = K' + 1

이때 비용은 다음과 같이 계산할 수 있다.

+K의 비용을 cost(K)라고 하자. 이 값은 규칙에 따라 K이다.

K의 일의 자리수가 0이면 K = K' * 2 인 K'가 존재한다
cost(K' * 2) = cost(K') = K / 2 이고 따라서
cost(K') = K / 2

K의 일의 자리수가 0 또는 1이면 K = K' + 1인 K'가 존재한다
cost(K' + 1) = cost(K') + 1 = K 이고 따라서
cost(K') = K - 1

쪼갤 수록 비용이 낮아지므로 최대한 쪼개는 것이 유리하다. 또한 비용이 더 많이 낮아지는 것은 K = K' * 2 일때 이므로, K의 일의 자리수가 0이면 무조건 이를 적용하여야 한다. 따라서 쪼개는 규칙은 다음과 같이 정하는 것이 최적이다.

K의 일의 자리수가 0이면
K = K' * 2

K의 일의 자리수가 1이면
K = K' + 1

0에서 N을 만드는 가장 간단한 방법은 규칙 1을 사용하는 것이다.

0 + N
cost: N

여기서 +N을 규칙에 따라 +1과 *2로 최대한 쪼개면 답을 얻을 수 있다.
예를 들어 1101을 쪼개보자.

0 + 1101
1101    = 1100 + 1  # cost(1101) = cost(1100 + 1) = cost(1100) + 1
1100    = 110 * 2   # cost(1100) = cost(110 * 2) = cost(110)
110     = 11 * 2    # cost(110) = cost(11 * 2) = cost(11)
11      = 10 + 1    # cost(11) = cost(10 + 1) = cost(10) + 1
10      = 1 * 2     # cost(10) = cost(1 * 2) = cost(1)
1       = 0 + 1     # cost(1) = cost(0 + 1) = cost(0) + 1
cost: 3

그런데 규칙을 따라 쪼개보면 일의 자리수가 0인 경우 누적되는 비용이 없고, 일의 자리수가 1이면 1만큼 누적되는 것을 볼 수 있다. 따라서 굳이 재귀할 필요 없이 답을 구할 수 있다. 답은 N을 이진법으로 나타낼 때 ‘1’의 개수가 된다.

구현

def solution(n):
    return bin(n).count('1')