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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

홀수, 짝수

 

---

 

코드

 

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;

    // 문제풀이 Tip
    // 점프, 순간이동의 순서를 고려하지 않아도 된다.(이 부분을 생각하기 힘들었다)
    // 도착위치에서 거꾸로 계산해 나간다.
    // 순간이동은 x2이기 때문에 /2로 되돌아간다고 생각한다.
    // 이 문제에서는 순간이동은 카운팅하지 않기 때문에 단순히 /2를 반복해도 문제되지 않는다.
    // 한칸 당 사용되는 배터리는 1이다. 한 번에 여러 칸을 이동하더라도 한칸 당 배터리 +1이라고 생각하고 풀면 된다. 

    while(n)
    {   //짝수
	    if(n % 2 == 0)
        {
            n /= 2;//순간 이동
	    }
        //홀수
        else
        {
            n -= 1;//거리 1만큼 이동
            ans++;//배터리 사용 +1
        }
    }

    return ans;
}

 

n에서 0으로 가는 방법 구하기

5 → 4 → 2 → 1 → 0 (2)

5
5 - 1 = 4   점프, 배터리+1
4 / 2 = 2
2 / 2 = 1
1 - 1 = 0   점프, 배터리+1

 

6 → 3 → 2 → 1 → 0 (2)

6
6 / 2 = 3
3 - 1 = 2    점프, 배터리+1
2 / 2 = 1
1 - 1 = 0    점프, 배터리+1

 

---

 

 

유사문제

 

https://www.acmicpc.net/problem/16953

16953번: A → B

---