[C++] 점프와 순간 이동

[문제]

코딩테스트 연습 - 점프와 순간 이동 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

현재 숫자에서 2를 나눌 수 있다면 계속 나눠주다가 못 나눈다면 1을 빼고 다시 2를 나눠주자. 2를 나눌때는 에너지를 안쓰니 최대한 많이 나눠주는것이 결국 가장 효율적인 길이 된다. 

[회고]

처음에 Dfs인가 했다가 범위가 10억인걸 보고 DP로 했는데 범위가 10억이라서 시간초과 + 메모리 초과가 떴다. 코드 자체의 문제는 없었지만 10억의 경우 n까지 가는 것만으로도 무리일 경우가 있으니 주의하도록 하자.

[코드]

#include <iostream>
using namespace std;

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

    return ans;
}