package Dynamic_programming;

import java.util.*;

public class beak_re_정수삼각형 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][n];
		
		for(int i=0; i<n; i++) { // 1번째줄에 1개, 2번째줄에 2개, 3번째줄에 3개...
			for(int j=0; j<i+1; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		for(int i=1; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(j == 0)
					arr[i][j] = arr[i][j] + arr[i-1][j];
				else if(j == n-1)
					arr[i][j] = arr[i][j] + arr[i-1][j-1];
				else 
					arr[i][j] =  arr[i][j] + Math.max(arr[i-1][j], arr[i-1][j-1]);
			}
		}
		
		int max = 0;
		for(int i=0; i<n; i++)
			max = Math.max(max, arr[n-1][i]);
	
		System.out.println(max);
		
	}
}

package BruteForce;

import java.util.*;

public class beak_로또 {

	static void comb(int arr[],boolean visited[], int start, int n, int r) {
		if(r==0) {
			for(int i=0; i<n; i++) {
				if(visited[i] == true)
					System.out.print(arr[i] + " ");
			}

			System.out.println();
			return ;
		}
		
		for(int i=start; i<n; i++) {
			visited[i] = true;
			comb(arr,visited,i+1,n,r-1);
			visited[i] = false;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			String a = sc.nextLine();
			if(a.equals("0"))
				break;
			
			String s[] = a.split(" ");
			int size = Integer.parseInt(s[0]);
			int arr[] = new int[size];
			
			for(int i=0; i<size; i++)
				arr[i] = Integer.parseInt(s[i+1]);
			
			boolean visited[] = new boolean[size];
			
			comb(arr,visited, 0,size,6); // start, n, r
			System.out.println();
		}//while
		
	}
}

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        int num = a*b*c;
        int arr[] = new int[10];
        
        String s = String.valueOf(num);
        for(int i=0; i<s.length(); i++){
            int k = Integer.parseInt(String.valueOf(s.charAt(i)));
            arr[k]++;
        }//for
        
        for(int i=0;i<10;i++)
            System.out.println(arr[i]);
    }
}

package Simulation;

import java.util.*;

public class beak_체스판다시칠하기 {

	static char arr[][];
	static char wb[][];
	
    private static int draw(int x, int y) {
        int min = Integer.MAX_VALUE;
        
        for(int i = 0; i < 2; i++) { // 0,1 두번
            int cnt = 0;
            for(int j = 0; j < wb[0].length; j++) { // 0~7까지
                for(int k = 0; k < wb[0].length; k++) { // 0~7까지
                    if(arr[x+j][y+k] != wb[(i+j)%2][k]) { // 들어온 값 x +(0~7)까지 더하고, y+(0~7)까지 더한다
                        cnt++;
                    }
                }
            }
            min = Math.min(min, cnt);
        }
        return min;
    }
	
    
	public static void main(String[] args) {
		Scanner sc = new  Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		arr = new char[n][m];
		
		sc.nextLine();
		
		//arr에 char형으로 전부 넣어놓기
		for(int i=0; i<n; i++) {
			String s = sc.nextLine();
			for(int j=0; j<m; j++)
				arr[i][j] = s.charAt(j);
		}
		
		wb= new char[2][8];
		wb[0] = "WBWBWBWB".toCharArray();
		wb[1] = "BWBWBWBW".toCharArray();
		
		int min = Integer.MAX_VALUE; //무한대
		
		for(int i=0; i<= n-8; i++) {
			for(int j=0; j<= m-8; j++)
				min = Math.min(min, draw(i,j));
		}
	
		System.out.println(min);
	}
}

package Stack_Queue;

import java.util.*;

// 30min
public class beak_균형잡힌세상 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			String s = sc.nextLine();
			
			if(s.equals("."))
				break;
			
			Stack<Character> stk = new Stack<>();

			for(int i=0; i<s.length(); i++) {
				if(s.charAt(i) == '[')
					stk.add('[');
				
				else if(s.charAt(i) == '(')
					stk.add('(');
                
				else if(s.charAt(i) == ']') {
					if(stk.size() !=0 && stk.peek() == '[')
						stk.pop();
					else {
						stk.add(']');
						break;
					}
				}
								
				else if(s.charAt(i) == ')') {
					if(stk.size() !=0 && stk.peek() == '(')
						stk.pop();
					else {
						stk.add(']');
						break;
					}
				}
			}
			
			if(!stk.isEmpty())
				System.out.println("no");
			else
				System.out.println("yes");
			
		} //.이면 break하고 나감
		
	}
}