점프와 순간 이동(실패 분석, java)

접근

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

일단 이 문제는 너무 어렵게 생각했던 거 같다.
처음에 든 생각은 BFS로 값을 넣는데

처음에 BFS(1,1)로 시작하고
뻗어나가는 가지가 +1이거나 현재 위치X2로 뻗어나가는 것이다.

+1인경우 Queue에 (현재위치+1,현재에너지+1) , 현재 위치X2인 경우 Queue에 (현재위치X2, 현재에너지) offer하는 것이었는데

시간 초과가 발생하였다.

왜냐하면 입력으로 주어지는 n이 1이상 10억 이하의 자연수이기 때문에
n번만 돌아도 1초가 걸리기 때문이다.

따라서 제한사항을 항상 주의깊게 봐서 방법을 선택하는 습관을 길러야한다.

맞은 풀이

import java.util.*;

public class Solution {
       public int solution(int n) {
        
        int ans = 0;
        
        //K칸 앞으로 점프, 현재 온거리의 x2에 해당하는 위치 순간이동
        // 점프하는 건 K만큼의 건전지 사용량, 순간이동은 줄지 않음
        // 순간이동하는 것이 효율적
        // N만큼 떨어진 장소로 가려고 한다.
        // 점프로 이동하는 것은 최소
        // 사용하는 건전지 사용량 최소로
      
        
        while(n!=0){
        // 1. n이 2로 나누어지면 2분의 1 만큼 감소
        if(n%2==0) n=n/2;
        // 2. n이 2로 나누어지지 않는다면
        else {
            // 건전지를 한칸 사용
            ans++;
            // n에 -1을 한다음 2로 나눠질 수 있는 수를 만든다.
            n--;
          }
        }
           
        
     
       return ans;
       
    }
 
    
}

틀린 풀이

import java.util.*;

public class Solution {
       static class Cost{
           int road;
           int energy;
           public Cost(int road, int energy){
               this.road = road;
               this.energy = energy;
           }     
       }
      
       static int min = Integer.MAX_VALUE;
    
       public int solution(int n) {
        
        
        //K칸 앞으로 점프, 현재 온거리의 x2에 해당하는 위치 순간이동
        // 점프하는 건 K만큼의 건전지 사용량, 순간이동은 줄지 않음
        // 순간이동하는 것이 효율적
        // N만큼 떨어진 장소로 가려고 한다.
        // 점프로 이동하는 것은 최소
        // 사용하는 건전지 사용량 최소로
      
      
        BFS(1,1,n);
           
        return min;
    }
    
    static void BFS(int start, int energy, int n){
        
        Queue<Cost> q = new LinkedList<>();
        
        q.offer(new Cost(start,energy));
        
        while(!q.isEmpty()){
            
            Cost c = q.poll();
            if(c.road==n){
                if(min>c.energy) min=energy;
                continue;
            }
            
            if(c.road+1 <=n){
                q.offer(new Cost(c.road+1,c.energy+1));
            }
            
            if(c.road*2<=n){
                q.offer(new Cost(c.road*2,c.energy));
            }
               
        }
        
        
    }
 
    
}