Baekjoon Algorithm | Problem 9095: 1, 2, 3 Addition

Tags:

Source

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

Problem

Solve Baekjoon Online Judge problem 9095, 1, 2, 3 Addition.

Input

Follow the input format and constraints given in the original problem statement.

Output

Print the answer required by the problem.

Sample Input 1

3 4 7 10

Sample Output 1

7 44 274

Algorithm Classification

  • Dynamic Programming

Solution

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ) {
            int T = Integer.parseInt(br.readLine());

            for (int t = 0; t < T; t++) {
                int n = Integer.parseInt(br.readLine());
                int[] dp = new int[11];

                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 4;

                for (int i = 4; i <= n; i++) {
                    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
                }

                bw.write(dp[n] + "\n");
            }
            bw.flush();
        }
    }
}