[c++] 프로그래머스 - 점프와 순간 이동(Level 2)

문제

코딩테스트 연습 - 점프와 순간 이동

 

코드

#include <iostream>
using namespace std;

// 점프: 베터리 듬, 순간이동: 배터리 안듬
// 거꾸로 계산
int solution(int n){
    int battery = 0;
    while(n>2){
        if(n&1){
            battery++;
            n--;
        }
        else n/=2;
    }
    return battery+1;
}

 

풀이

처음에 백트랙킹으로 완전 탐색을 해볼까 싶었지만 너무나도 큰 입력값에 포기하고, 규칙을 찾아보려고 했습니다. 이 문제는 0에서부터 출발하는 게 아니라 n에서부터 거꾸로 0을 만든다고 생각하면 쉽습니다. 현재 거리가 짝수일 때는 순간이동이기에 2로 계속 나눠주고, 홀수일 때는 -1을 해주어 점프를 합니다.

최종적으로 1에서 0으로 가기 위해서는 항상 점프를 해야 하니 return 값에 +1을 해주어 반환합니다.