문제
접근
순간이동(x2)는 건전지 소모가 없다.
목표는 건전지 소모를 최소화하는 것이므로, 가능한 경우에는 항상 순간이동을 이용하는 것이 최선의 결과를 가져올 것이다.
목표 지점인 n부터 시작해서 0으로 거꾸로 이동하며 순간이동이 불가능한 경우(홀수인 경우)에만 점프를 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
def solution(n):
ans = 0
while n != 0:
if n % 2 == 0:
n //= 2
else:
n -= 1
ans += 1
return ans
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int solution(int n)
{
int ans = 0;
while(n!=0){
if(n%2==0){
n /= 2;
}
else{
n--;
ans++;
}
}
return ans;
}