[Programmers] 점프와 순간이동

점프와 순간이동

점프와 순간이동 을 클릭하면 바로 이동한다.

이번 문제는 조~금 생각을 해야하는 문제였다. 설명하기는 조금 길어 상세한 문제를 보고 싶으면 위 링크를 눌러 보자!

간단히 정리하자면 N 까지의 거리를 이동하고 싶을때 점프는 1칸, 순간이동은 현재 위치 X 2 칸으로 이동한다.

하지만 점프를 하는 경우 건전지를 소모한다 ! ‘최소한의 건전지를 사용해 이동해보자’ 라는 문제이다..

‘건전지를 최소한으로 사용해보자’ 하지만 그냥 ‘최소한의 점프로 가보자’ 로 이해하면 될 것 같다.

처음엔 정말 멍 했다.. 어떻게 접근해야할지 감도 안왔지만 역시 여러 경우를 손으로 해보며 규칙을 찾는게

가장 베스트 방법인 것 같다. 그래서 N 이 3, 7, 10, 19 인 경우를 해보는데 규칙이 보였다.

바로 순간이동은 두 배씩 이동을 하는 방법 이기때문에 목표 거리를 1이 될때 까지 계속 반으로 나누고

만약 값이 홀수라면 버림을 해준 뒤 버림을 한 경우에만 점프를 하면 됐다.

예를 들어 N 이 19인경우, 19 / 2 = 9 / 2 = 4 / 2 = 2 / 2 = 1 이런 식이 나오는데 여기서 19, 9 가 홀수이다.

따라서 1로 가기위해 점프는 무조건 한 번 해야하고 그 뒤에 점프를 두 번 더해 총 세 번의 점프가 답으로 나온다.

import math

def solution(n):
    ans = 0

    # n을 1이 될때 까지 2로 나누고 값이 홀수이면 버림하고 ans를 1 올린다.
    while n >= 1:
    	if n % 2 == 0:
    		n = n/2
    	else:
    		n = math.floor(n/2)
    		ans += 1
    return ans

위 코드를 통해 100점을 맞고 다른 사람 풀이를 보는데 정말 충격이였다..

앞서 주저리 주저리 설명했지만 결국 저 방법은 10진수를 2진수로 바꾸는 과정이다.

19를 2진수로 바꾼다면 10011이고 7을 2진수로 바꾼다면 111 이다.

아주아주 단순하게 N 을 2진수로 바꾼 후 1의 개수를 세면 그것이 바로 최소한의 점프 수였다..

그래서 solution 함수는

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

이렇게 바꿀 수 있다. 이번 문제를 풀면서 정말 뒷통수를 맞은 듯 한 기분이 들었다..

조금 더 생각을 바꾸고 한 번 더 생각해보는 능력을 길러야겠다.

내가 생각한 방법이 2진수로 바꾼 뒤 1의 개수를 세면 된다는 것과 같은 방법일줄은 생각도 못했다.