15988 1,2,3 더하기 (JAVA)

• 계단오르기와 동일한 Dynamic Programming 기본 문제이다.

• 주의점 1
  입력의 범위가 1에서 시작한다는 점.
  따라서 입력이 1,2,3 일 경우에는 미리 반환을 해줘야 함.
• 주의점 1
  입력의 최댓값인 1,000,000은 double 자료형의 크기도 초과하는 결과를 반환한다.
  다행히도 문제의 조건에따라 결과를 1,000,000,009 로 나눈 나머지를 출력하기 위해, 각각의 계산마다 나머지연산을 추가한다.

import java.util.*;

public class Main {

    static long dp(int n){
        long[] arr = new long[n+1];
        arr[1] = 1;
            if(n==1)
                return arr[1];
        arr[2] = 2;
            if(n==2)
                return arr[2];
        arr[3] = 4;
            if(n==3)			// 1~3 의 입력이 들어올 경우를 처리
                return arr[3];
        for(int i=4; i<=n; ++i){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
            if(arr[i] >= 1000000009)	// 각 계산마다 나머지 연산 수행
                arr[i] = arr[i] % 1000000009;
        }
        return arr[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n-->0){
            System.out.println(dp(sc.nextInt()));
        }
    }
}