package Dynamic_programming;

import java.util.*;

public class beak_1로만들기 {

	//50 min
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int dp[] = new int[n+1];
		Queue<Integer> qu = new LinkedList<>();
		qu.add(n);
		
		while(!qu.isEmpty()) {
			n = qu.poll();
			
			if(n == 1) {
				System.out.println( dp[1] );
				break;
			}
			
			
			if(n%3==0 && dp[n/3]==0) { //dp[n]==0일떄 방문해야 최소, 방문했던곳은 안간다 -> n은 이미 방문했던 곳이라 값이 있고 n/2, n/3을 확인해야한
				int k = n/3;
				dp[k] = dp[n] +1;
				qu.offer(k);
			}
			if(n%2==0 && dp[n/2]==0) {
				int k = n/2;
				dp[k] = dp[n] +1;
				qu.offer(k);
			}
			if(dp[n-1]==0) { //n 아니고  n-1이잖아 조건 잘 봐줘!
				int k = n-1;
				dp[k] = dp[n] +1;
				qu.offer(k);
			}
			
			
		}//while
		
	}
}

package Stack_Queue;

import java.util.*;

public class prog_2_캐시 {

	//은근 잔 조건들이 많네...; 40min
	  static public int solution(int cacheSize, String[] cities) {
	      int answer = 0;
	      LinkedList<String> qu = new LinkedList<String>();
	      
	      String real[] = new String[cities.length];
	      
	      for(int i=0;i<cities.length; i++)
	    	  real[i] = cities[i].toUpperCase();
	      
	      if(cacheSize == 0)
	    	  return cities.length * 5;
	      
	      for(int i=0;i<cities.length; i++) {
	    	  String an = real[i];
	    	  System.out.println(an);
	    	  
	    	  if(qu.size() < cacheSize) {
	    		  if(qu.contains(an)) {
	    			  int idx = qu.indexOf(an);// 위치 찾아서
	    			  qu.remove(idx); // 제거하고
	    			  qu.add(an); //위에 새로 추가
	    			  
	    			  answer = answer+1;
	    		  }
	    		  else {
	    			  qu.add(an); //위에 새로 추가 
	    			  answer = answer +5;
	    		  }
	    	  }
	    	  
	    	  else if( qu.size() >= cacheSize){
	    		  if(qu.contains(an)) {
	    			  int idx = qu.indexOf(an);// 위치 찾아서
	    			  qu.remove(idx); // 제거하고
	    			  qu.add(an); //위에 새로 추가
	    			  
	    			  answer = answer+1;
	    		  }
	    		  else {
	    			  qu.remove(0); //맨 앞이 제일 오래된 데이터
	    			  qu.add(an); //위에 새로 추가 
	    			  answer = answer +5;
	    		  }	    		  
	    	  }
	    	  
	      }//for
	      
	      return answer;
	  }
	  
	  public static void main(String[] args) {
		String s[] = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
		System.out.println(solution(3, s));
	  }
	  
}

package Dynamic_programming;

public class prog_3_멀리뛰기 {

	static public long solution(int n) {
		      
		      long dp[] = new long[2001];
		      dp[1] = 1;
		      dp[2] = 2;
		      
		      for(int i=3;i<=2000; i++)
		    	  dp[i] = (dp[i-1] + dp[i-2]) %1234567;
		      
		      return dp[n];
	  }
	
	public static void main(String[] args) {
		System.out.println(solution(2000));
	}
}

package Stack_Queue;

import java.util.*;

public class prog_3_이중우선순위큐 {

    static public int[] solution(String[] operations) {
        LinkedList<Integer> realqu = new LinkedList<Integer>();
        int answer[] = {0,0};
        
        for(int i=0;i<operations.length; i++) {
            Collections.sort(realqu,Collections.reverseOrder());
        	String a[] = operations[i].split(" ");
        	
        	System.out.println(realqu);
        	
        	if(a[0].equals("I")) {
        		realqu.add(Integer.parseInt(a[1]));
        	}
        	
        	if(a[0].equals("D") && a[1].equals("1")) {
        		if(realqu.isEmpty())
        			continue;
        		
        		realqu.remove(0);
        	}
        	
        	if(a[0].equals("D") && a[1].equals("-1")) {
        		if(realqu.isEmpty())
        			continue;
        		
           		realqu.remove(realqu.size()-1);
        	}
        	
        }
        
        //매번 reverse 해줘야 한다는 점 잊지말자!
        Collections.sort(realqu,Collections.reverseOrder());
        
        if(realqu.isEmpty()) {
        	answer[0] = 0;
        	answer[1] = 0;
        }
        else {
        	answer[0] = realqu.get(0);
        	answer[1] = realqu.get(realqu.size()-1);
        }
        
        return answer;
    }
	
    
	public static void main(String[] args) {
		String a[] = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
		solution(a);
	}
}

package Dynamic_programming;

public class beak_123더하기 {

	public static void main(String[] args) {
		int arr[] = new int[12];
		
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		arr[3] = 4;
		
		for(int i=4;i<=11;i++) 
			arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			int a = sc.nextInt();
			System.out.println(arr[a]);
		}
		
	}
}