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

문제

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return 하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

 

입력 & 출력

입출력 예

Nresult

5	2
6	2
5000	5

새로 사용한 함수

a,b = divmod(x, y)

몫과 나머지를 한꺼번에 반환해주는 함수 

보통은 //와 %를 사용하여 구성할 수 있습니다.

 

풀이 과정

1. 1부터 숫자를 차례대로 넣으면서 생각해보니 숫자가 아무리 커도 2로 나누는 결괏값에 따라서 반환 값을 유추할 수 있었습니다.

 

2. 일단 탈출 조건은 2로 나누었을 때 몫이 1인 경우인데 이럴 경우 나머지가 1일 경우에는 직접 한번 점프를 해야 하기 때문에 반환하는 ans값에 1을 더해주고 0일 경우에는 점프는 할 필요 없기 때문에 바로 while문을 탈출해 줄 수 있도록 합니다.

 

3. 탈출 조건을 정의해주고 나머지 두 가지 경우를 살펴보면 몫이 1보다 크면서 나머지가 1이 남는 경우가 있는데 이럴 경우에는 나머지만큼 한 칸 점프를 해주어야 배터리 소모를 최소화할 수 있어서 ans 값을 1 증가시켜줍니다.

 

4. 마지막 조건으로는 몫은 1보다 크고 나머지가 없는 경우인데 이때는 순간 이동만 한 경우로 배터리를 쓸 필요가 없으니 2로 다시 나눠주게 하고 while문을 반복해줍니다.

 

코드

def solution(n):
    check, remain = divmod(n, 2)
    ans = 1
    while (check):
        if check == 1 and remain == 1:
            ans += 1
            break
        elif check == 1 and remain == 0:
            break
        elif check > 1 and remain == 1:
            check, remain = divmod(check, 2)
            ans += 1
        else:
            check, remain = divmod(check, 2)
    return ans