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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

처음에는 동적계획법으로 해결해야한다고 생각했지만, 조금 더 생각해보니 그리디로 해결할 수 있는 문제임을 알 수 있었다. 순간이동을 하는 경우에는 건전지를 사용하지 않기 때문에 순간이동을 최대한 많이 해야한다는 것을 쉽게 알 수 있다. N에서부터 0으로 간다고 생각했을 때, 순간이동을 최대한 많이 하려면 현재위치가 짝수인 경우에는 2로 나눠주고, 현재 위치가 홀수인 경우에는 짝수로 만들어준다. 이 때 홀수에서 1을 빼면 짝수가 되므로 건전지 1만 사용하고도 짝수를 만들 수 있다.

코드

#include <iostream>
using namespace std;

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