<Algorithm> 20. 9095번 1,2,3 더하기

1. 9095번 1,2,3 더하기

• 재귀나 DP로 풀 수 있는 문제( DP[N] = DP[N+1] + DP[N+2] + DP[N+3] )

• 재귀는 모든 경우의 수를 탐색해야 할 경우에 사용 ( 모든 경우 탐색 -> 답에 해당하는 경우의 수를 출력 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
 
    static int count;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        ArrayList<Integer> res = new ArrayList<>();
        
        for(int T = 0; T < N; T++) {            
            count = 0;
            int num = Integer.parseInt(br.readLine());
            recursion(0, num);
            res.add(count);
        }
        for(int i = 0; i < res.size(); i++)
            System.out.println(res.get(i));
        
    }
    private static void recursion(int total,int num) {
        if(total == num) { // 나타낼수 있는경우 count ++
            count++;
            return;
        }
        
        if(total + 1 <= num) { // 재귀
            recursion(total + 1, num);
        }
        if(total + 2 <= num) {
            recursion(total + 2, num);
        }
        if(total + 3 <= num) {
            recursion(total + 3, num);            
        }
    }
    
}