package Math;

import java.util.*;

public class beak_방번호 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.nextLine();
		
		int arr[] = new int[10];
		
		for(int i=0;i<s.length();i++) {
			int k = s.charAt(i)-'0';			
			if(k==9)
				arr[6]++;
			else
				arr[k]++;
		}

        
		int max = 0;
        arr[6] = Math.round(arr[6]/2.0f); // 반올림!!!!!!!
        for(int i=0;i<10;i++)
            max=Math.max(max, arr[i]);
        
		System.out.println(max);
	}
}

package Greedy;

import java.util.*;

public class beak_대회or인턴 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		
		//k==0: 인턴 0이면 적게 만들 수 있는 팀으로 나간다
		//k!=0: 인턴으로 나가야 하는 인원이 있다면 -> 인원만큼 빼고 팀으로 나갈 수 있는 인원 체크
		System.out.println( Math.min(Math.min(n/2, m), (m+n-k)/3));
		
	}
}

package Greedy;

import java.util.*;

//35
public class beak_30 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.nextLine();
		
		int arr[] = new int[10]; //9까지 담아야함
		int sum = 0;
		
		for(int i=0;i<a.length(); i++) {
			arr[a.charAt(i)-'0']++;
			sum = sum + a.charAt(i)-'0';
		}
		
		//30의 배수가 되는 조건
		//1) 각 자리수의 합이 3의 배수이다
		//2) 0의 개수가 1개 이상인 모든 조건을 만족할때만 true
		if(sum%3 !=0 || !a.contains("0")) {
			System.out.println(-1);
			return;
		}
		
		//string을 쓰는 것과 stringBuilder를 쓰는 것에 약 10배의 ms차이가 났다
		StringBuilder s = new StringBuilder();
		for(int i=9; i>=0; i--) {
			while(arr[i]>0) {
				s.append(i);
				arr[i]--;
			}
		}
		System.out.println(s.toString());
	}
	
}

package Dynamic_programming;

import java.util.*;

//1h
public class beak_쉬운계단수 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long dp[][] = new long[101][11];
		
		for(int i=1;i<=9;i++)
			dp[1][i] = 1; //자리수 1은 전부 값 ->1
		
		for(int i=2;i<=n;i++) {
			dp[i][0] = dp[i-1][1];
			
			for(int j=1; j<=9; j++) { //9까지 해야 10의 값도 구할 수 있음
				dp[i][j] = (dp[i-1][j-1] +dp[i-1][j+1]) % 1000000000;
			}
			
		}
		
		long ans = 0;
		
		for(int i=0; i<=9; i++)
			ans = ans + dp[n][i];
		
		System.out.println(ans%1000000000);
	}
}

package Dynamic_programming;

import java.util.*;

//16 min
public class beak_이친수 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//값이 클 수 있으므로 int형이 아닌 long형으로 선언
		long dp[] = new long[91];
		
		dp[1] = 1;
		dp[2] = 1;
		
		for(int i=3;i<=90; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		System.out.println(dp[n]);
	}
}