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

문제

[C++] 프로그래머스: 점프와 순간 이동 LV.2
https://school.programmers.co.kr/learn/courses/30/lessons/12980

 

---

 

접근 방법

이 문제는 점프(+1)는 비용이 들고, 순간이동(*2)은 비용이 들지 않는다는 점이 핵심이다.
따라서 가능한 한 순간이동을 최대한 활용하는 방향으로 생각해야 한다.

 

0에서 n으로 가는 과정보다, n에서 0으로 거꾸로 내려오는 방식으로 접근하면 훨씬 단순해진다.

• 현재 값이 짝수라면
  → 직전에 순간이동을 통해 왔다고 볼 수 있으므로
  → n /= 2 만 수행한다.
• 현재 값이 홀수라면
  → 순간이동이 불가능하므로
  → n - 1로 이동하며 점프를 한 번 사용한다.

이 과정을 반복하면, 결국 홀수일 때 사용한 점프의 횟수가 최소 에너지 소모량이 된다.

 

구현 시 주의할 점

• 이 문제는 BFS나 DP로 풀 필요가 없다.
  나누기 2 연산을 사용하면 n이 빠르게 줄어들어 시간 복잡도는 O(log n) 수준이다.
• 반복문의 종료 조건과 초기값을 잘 맞춰야 한다.
  (n > 1인지, n > 0인지에 따라 ans 초기값이 달라질 수 있다.)
• 처음에 점프를 한 번 한 상태에서 시작하기 때문에 ans = 1로 초기화한다.
  그래야지 1 → 2 → 4 → 8 ... 이렇게 *2를 할 수 있다.

 

---

 

코드

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 1;
    while(n > 1)
    {
        if(n % 2 != 0)
        {
            n--;
            ans++;
        }
        else
            n /= 2;
    }

    return ans;
}