BOJ 9095 1, 2, 3 더하기

문제 풀이 방식

• 아무리봐도 가방문제랑 비슷하고 DP여서 알고리즘을 보니 DP였다.
• 점화식 : DP[n] = DP[n-1] + DP[n - 2] + DP[n - 3];

문제 풀이 (Java)

• 처음에 효율성 문제 있었던 코드 :

import java.io.IOException;  
import java.util.*;  
public class boj9095 {  
  
    static int[] DP = new int[11];  
  
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(System.in);  
        int T = sc.nextInt();  
  
        DP[1] = 1;  
        DP[2] = 2;  
        DP[3] = 4;  
  
        for(int i = 0 ; i < T ; i++){  
            int N = sc.nextInt();  
  
            for(int j = 4 ; j <= N ; j++){  
                DP[j] = DP[j - 1] + DP[j - 2] + DP[j - 3];  
            }  
  
            System.out.println(DP[N]);  
        }  
    }  
}