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

문제

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

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

 

문제 내용

문제에 나와있는 대로, 0번 위치에서 N번 위치까지 이동해야 한다.

이때 현재 있는 위치*2 인 곳으로 갈 때에는 건전지가 소모되지 않지만,

현재 있는 위치+k 인 곳으로 갈 때에는 k만큼의 건전지가 소모된다.

건전지 소모를 최소한으로 하여 N번 위치까지 이동하고자 할 때, 건전지 사용량을 출력하면 된다.

 

문제 풀이

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

문제를 이해해 보기 위해 0~19까지 건전지 소모량을 적어보았다.

빨간색은 이전 위치에서 X2 한 경우이고, 파란색은 +1을 한 경우이다.

잘 살펴보면, 짝수 인덱스는 모두 X2를 통해 도달할 수 있고, 홀수 인덱스는 바로 앞 인덱스에서 +1을 하면 도달할 수 있다.

 

숫자 N의 범위가 1~10억 이기 때문에 배열로 선언해 두고 풀기엔 좀 어려워 보인다.

위 그림은 dp방식처럼 보이지만, 잘 생각해보면 거꾸로 거슬러 0번으로 되돌아가는 방법으로 풀 수 있다.

짝수이면 /2 를 하면 되고, 홀수이면 -1을 하면 된다. 

이때 이동 카운트는 -1을 할 때에만 해주면 된다.

 

코드

#include <iostream>
using namespace std;

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