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

쉽게 생각하면 안 풀리고 한 번 더 생각해야 한다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <vector>

using namespace std;


//n : 위치, k : 목표, cnt : 건전지소모
int func(int n, int k, int cnt){
    if(n == k){
        return cnt;
    }
    //정수면서 2로 나눠지나
    cout << n << " ";
    if(n/2 >= k && n%2 == 0){
        return func(n/2, k, cnt);
    }else{
        return func(n-1,k, cnt+1);
    }
}

int solution(int n)
{
    int ans = 0;
    ans = func(n,1,1);


    return ans;
}

 

상향식 접근은 틀린데

하향식 접근은 맞다.

 

다시 말해서 1부터 답까지 찾아가는 것은 최적해를 보장하지 않는데

답에서 1로 내려오는 것은 최적해를 보장한다.

 

생각해보면 위의 말이 틀렸단 것을 알 수 있는데

그냥 하위의 모든 경우를 고려하지 않았기 때문에 1부터 찾아갈 때 틀린 것이지

Top-down이나 Bottom-up이나 최적해가 나올 수 있다.

 

다만 10억이고 DP table로 하기엔 그렇고..

숫자가 클 때 빨리 찾아내는 Binary의 특성을 생각해봤다.

Binary Search도 숫자가 클 때 특정 숫자를 정말 빨리 찾아낸다.