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

문제 제목 : 점프와 순간이동

문제 출처 : 프로그래머스

알고리즘 : Math

문제원본링크

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

프로그래머스

def solution(N):
    answer = 0
    while N > 0:
        answer += N % 2
        N //= 2
    return answer

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

처음 위치는 0 에서

N 만큼 떨어진 장소로 가기 위해

최소한으로 소모해야하는 건전지양은 얼마일까요?

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

K칸 앞으로 점프(건전지가 K 만큼 감소)하거나

지금까지 온 거리의 2배에 해당하는 위치로 순간이동(건전지 사용 X)이 가능합니다.

 

사고를 전환해서

0에서 시작하지 않고 역으로 N에서 시작하여 0으로 가볼까요?

N까지 최소의 건전지 사용량으로 가는 방법은

최대한 순간이동을 많이 해서 건전지를 아예 사용하지 않는 방법 아닐까요?

n = N

(1) n이 2의 배수이면, 순간이동을 통해 n//2의 위치로 이동합니다. 

     n //= 2

(2) n이 2의 배수가 아니면, 점프로 n-1로 이동하고, 사용한 건전지 양을 1++해줍니다.

      n -= 1

      used_battery += 1

(3) n이 0이 될때까지 (1) / (2) 를 반복합니다.

n = N

while n:
	
    used_battery += (n % 2)
    n //= 2

 

 

이 과정은 사실 십진수를 이진수로 표현할 때 코드와 동일합니다.

하단의 십진수에서 이진수로 변환하는 코드의 마지막 부분을 보시면 

이진수 표현을 저장하던 two 변수를 reverse하는 모습을 볼 수 있습니다.

이 부분이 우리가 0이 아닌 N에서 부터 시작한 것과 동일한 원리라고 보실 수 있습니다.

while 문 안을 보시면 처음에 우리는 ten_num에서 2를 나눠줍니다. 

그 다음번에 우리는 또 2를 나눠주게됩니다.

우리 입장에서 보면 2를 나눠주는 것이지만 ten_num 입장에서는 두번째에 나눈 2는, 2가 아니라 4가 나눠지게 된 셈입니다.

처음에 2를 한번 나눔(이진수의 첫번째 자리수) -> 2를 두번째로 나눔 (이진수의 두번째 자리수) -> 세번 나눔 (이진수의 세번째 자리수)

* 해당 자리수는 마지막 숫자 기준입니다. (예시 - 1010101 <- 이 아이를 첫번째라고 했을때)

# 십진수에서 이진수로 변환
ten_num = N
two = ''

while ten_num:

	two += str(ten_num % 2) 
	ten_num //= 2
    
print(two[::-1])

 

추천 유사 문제 : 

https://www.acmicpc.net/problem/1094

1094번: 막대기