[백준] 9095: 1, 2, 3 더하기 JAVA

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

---

풀이과정

이 문제는 Dynamic Programming(DP) 을 사용해서 푸는 문제이다.

 

DP

하나의 큰 문제를 여러개의 작은 문제로 나눠서 해결하는 것. 한 값을 이 전에 구해놓은 값들을 사용하여 구할 수 있을 때 사용한다.

 

풀이 핵심

1. 1, 2, 3, 4, ... 를 순서대로 적으며 점화식 찾기
2. dp[4]의 경우 1+dp[3], 2+dp[2], 3+dp[1] 이런 식으로 된다.
3. 점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이다. 이를 코드로 구현한다.

---

최종 코드

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static int[] arr = new int[11];
    public static void main(String[] args) throws IOException {
        calc();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(arr[n]+"\n");
        }
        bw.flush();
    }

    public static void calc(){
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        for(int i = 4; i < arr.length; i++){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
    }
}