Level 2. 점프와 순간이동

점프와 순간이동

코딩테스트 연습 > Summer/Winter Coding(~2018) > 점프와 순간이동

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

문제 설명

# 문제 본문

거리가 N 만큼 떨어져 있는 장소로 가려고 한다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 한다. 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수 구현

# 제한 사항
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수

문제 풀이

01. 첫번째 시도: Divmod(a,b)를 이용

# 01. Using divmod(a,b)
# Input value
n = 5000
answer = 0
# Process
while n > 0:
    v, i = divmod(n,2) # Divide n to 2
    n = v # Update n to v
    answer += i # add i
answer

건전지 사용량을 최소화 하기위해, 두배(x2)의 이동을 보이는 케이스를 최대화 해야합니다.
즉, 목표값 N을 2로 나누며 발생하는 나머지의 값을 answer에 합하면 됩니다.

위의 과정을 다시 살펴보면 결국, 이진화를 통해 나오는 값의 1의 갯수를 구하면 된다는 것을 알 수 있었습니다.

02. 두번째 시도: bin().count('1') or format(,'b').count('1')를 이용

# 02. Using bin number
# Input value
n = 5000
# Process
print(bin(n).count('1'))

전체 코드

#01 Using divmod(a,b)
def soultion(n):
    answer = 0
    while n > 0:
        v, i = divmod(n,2)
        n = v
        answer += i
    return answer
    
#02 Using bin number.count('1')
def solution(n):
    return bin(n).count('1') # or return format(n,'b').count('1')