백준 9095번 1, 2, 3 더하기(JAVA)

문제

9095번: 1, 2, 3 더하기

 

풀이

import java.io.*;

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

        int T = Integer.parseInt(br.readLine());
        int[] ans = new int[11]; // 0 < n < 11

        ans[1] = 1;
        ans[2] = 2; // 1 + 1 or 2
        ans[3] = 4; // 1 + 1 + 1 or 1 + 2 or 2 + 1 or 3

        // 모든 n에 대해 계산을 한다.
        for (int i = 4; i < 11; i++) {
            // n = 4이면 (1을 만드는 방법) + 3, (2를 만드는 방법) + 2, (3을 만드는 방법) + 1 로 풀어낼 수 있다.
            // n = 5일 때 1, 2, 3을 제외한 숫자를 사용하지 않으므로 (1을 만드는 방법) + 4를 고려하지 않는다.
            ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
        }

        // 이미 계산을 완료하였으므로 n을 만드는 방법 수를 출력한다.
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            bw.append(String.valueOf(ans[n]));
            bw.newLine();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}