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

알고리즘/프로그래머스

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

lheunoia 2022. 2. 21. 18:16

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

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

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈

programmers.co.kr

이번 문제는 Top-Bottom 문제였습니다.

《문제 풀이》

1. 처음 한 칸은 무조건 점프해야 하므로 ans 1 부터 시작

2. n을 2로 나누었을 때 나머지가 1이면 점프해야 한다는 의미이므로 ans++

《C++ 코드》

#include <iostream>

using namespace std;

int solution(int n)
{
    int ans = 1; // 한 칸은 무조건 점프
    
    while (n != 1) {
        if (n % 2 == 1) { // 순간이동을 할 수 없다면
            ans++;
        }
        n /= 2;
    }
    
    return ans;
}