백준 15988 자바 - 1, 2, 3 더하기 3

문제

---

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

 

 

문제해결

---

https://broship.tistory.com/219

- 백준 9095 문제와 똑같은 문제다, 다만 n의 최대값이 1000000으로 바뀌었다

- 처음 dp 배열을 1000000 크기로 생성 후 오버플로우를 방지하기 위해 모든 덧셈을 한 후 1000000009을 나눠주면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dp = new int[1000001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i < 1000001; i++) {
            dp[i] = ((dp[i-3] + dp[i-2]) % 1000000009 + dp[i-1]) % 1000000009;
        }

        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}