문제 링크

링크텍스트
실버 3
다이나믹 프로그래밍

풀이 1

1. i를 1부터 3까지 반복하면서 재귀를 돈다.
2. i를 더한값 val이 입력된 n과 같으면 cnt를 올려주고 return 해준다.
3. val이 n보다 크다면 return해서 다시 재귀해준다.
   태그는 DP로 되어있지만 재귀로 풀었다. val이 n보다 더 큰경우 그다음 i를 더해도 무조건 초과가 되기때문에 이부분을 생략해주면 시간을 줄일 수있을것 같다.

코드

import java.util.*;
public class Main {

	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	public static int[] arr,visited,arr3;
	static int N,T,num=0,cnt=0;
	static boolean flag;
    public static void main(String[] args) {
    	//입력
    	T=scan.nextInt();
    	for(int i=0;i<T;i++) {
    		N=scan.nextInt();
    		cnt=0;
    		int ans=cal(N,0);
    		sb.append(ans+"\n");
    	}
    	System.out.print(sb);
    


    }
    static int cal(int n, int val) {
    	//basecase
    	if(val==n) {
    		cnt++;
    		return 1;
    	}
    	if(val>n) {
    		return 1;
    	}
    	for(int i=1;i<=3;i++) {
    		cal(n,val+i);
    	}
    	
    	return cnt;
    }
    

 }