package Dynamic_programming;

//20min
import java.util.*;

public class beak_123더하기3 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long dp[] = new long[1000001];
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for(int i=4; i<=1000000; i++) {
			dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009;
		}
		
		int n = sc.nextInt();
		for(int i=0; i<n; i++) {
			int k = sc.nextInt();
			System.out.println(dp[k]);
		}
	}
}

package DP;

import java.util.*;

public class beak_123더하기_re {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//정수 n을 1,2,3으로 나타내는 법
		int dp[] = new int[11];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
			
		for(int j=4; j<=10; j++) {
			dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
		}
		
		int n = sc.nextInt();
		
		for(int i=0; i<n; i++) {
			int num = sc.nextInt();
			System.out.println(dp[num]);
		}

	}
}

package DP;

import java.util.*;
public class beak_re_퇴사 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int t[] = new int[n+2];
		int p[] = new int[n+2];
		
		for(int i=1; i<=n;i++) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}
	
		int dp[] = new int[n+2];
		for(int i=n; i>=1; i--) {//끝에서부터
			int day = i +t[i]; //일 끝나는 시간
			
			if(day <=n+1) // 끝나는 시간이 n안쪽이면 (k라면) k 날의 값도 가질 수 있다
				dp[i] = Math.max(p[i] + dp[day], dp[i+1]);
			else // 시간안에 못끝나는 일이면
				dp[i] = dp[i+1]; // 자기자신은 값을 못가지니까 다음날의 값, 만약 다음날도 값이 없다면? 계속 0이겠지
		}
		
		System.out.println(dp[1]);
		
	}
}

package Dfs_Bfs;

import java.util.*;

public class beak_섬의개수 {
	
	public static void dfs(int arr[][], int x, int y) {
		arr[x][y] = 0;
		
		int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1};
		int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1};
		
		for(int i=0; i<8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && nx<arr.length && ny>=0 && ny<arr[0].length
					&& arr[nx][ny] !=0)
				dfs(arr, nx,ny);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			
			if(n == 0 && m==0)
				break;
			
			if(n ==1 && m==1) {
				int k = sc.nextInt();
				if(k == 0)
					System.out.println(0);
				else
					System.out.println(1);
				
				continue;
			}
			
			int arr[][] = new int[n][m];
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++)
					arr[i][j] = sc.nextInt();
			}
			
			int answer = 0;
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++){
					if(arr[i][j] !=0) {
						dfs(arr,i,j);
						answer++;
					}
				}
			}//dfs
			
			System.out.println(answer);
		}
	}
}

import java.util.*;

class Solution {
  public int solution(String dartResult) {
      int answer = 0;
      LinkedList<Integer> list = new LinkedList<>();
      
      //무조건 숫자 + STD + * 
      for(int i=0; i<dartResult.length(); i++){
          char c = dartResult.charAt(i);
          
          if(c =='0' || c =='1' ||c =='2' ||c =='3' ||c =='4' ||c =='5' ||c =='6' ||c =='7' ||c =='8' ||c =='9'){
              if(i+1 <dartResult.length() && dartResult.charAt(i+1) =='0'){
                  list.add(10);               
                  i++;
              }
              else
                  list.add(Integer.parseInt(String.valueOf(c)));
          }
          
          else if(c == 'T'|| c == 'D' || c=='S'){
              if(c == 'D'){
                  int n = list.removeLast();
                  list.add(n*n);
              }
              else if(c == 'T'){
                  int n = list.removeLast();
                  list.add(n*n*n);
              }   
          }
          
          else{
              if(c == '*'){
                  if(list.size()==1){
                      int n = list.removeLast();
                      list.add(n*2);
                  }
                  else if(list.size()>=2){
                      int n1 = list.removeLast();
                      int n2 = list.removeLast();
                      
                      list.add(n2*2);
                      list.add(n1*2);
                  }
              }
              
              if(c == '#'){
                  int n = list.removeLast();
                  list.add(n*-1);
              }
          }    
      }
      
      for(int i=0; i<list.size(); i++)
          answer += list.get(i);
      
      return answer;
  }
}