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

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

프로그래머스

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;
int sol(int n, int battery)
{
    if(n==0)
        return battery;
    else if(n%2==0)
        return sol(n/2,battery);
    else
        return sol(n-1,battery+1);
}

int solution(int n)
{
    int ans = 0;
    ans=sol(n,0);
    return ans;
}

 

 

풀이 방법

0부터 DFS를 돌리면 시간초과가 난다.

N이 10억 이하의 자연수라서 그렇다. 그렇다고 DP를 쓰자니 10억 배열... 안된다.

반대로 N에서부터 시작하여 줄여나가면 된다.

N에서 2로 나누어진다면 순간이동을하여 연료를 아끼고

2로 나누어지지 않는다면 어쩔 수 없이 연료를 사용하여 이동해야 한다.

 

 

 

 

 

아래의 코드는 DFS로 풀었다 시간초과가 난 코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
int sol(int cur, int n, int battery)
{
    if(cur==n)
        return battery;
    else if(cur>n)
        return 1000000001;
    else
        return min(sol(cur+1,n,battery+1), sol(cur*2,n,battery));
}

int solution(int n)
{
    int ans = 0;
    ans=sol(1,n,1);
    return ans;
}