9095

1 + 2 + 3으로 나타내기 : https://www.acmicpc.net/problem/9095

 

기존엔 다이나믹으로 풀이 

d[i] = d[i-3] + d[i-2] + d[i-1]

 

완전 탐색 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int[] arr;
	static int[] nums = { 1, 2, 3 };
	static int answer;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N =  Integer.parseInt( br.readLine() );
		arr = new int [N];
		for ( int i = 0 ; i < N ; i ++) {
			answer = 0 ;
			dfs(0, Integer.parseInt( br.readLine()));
			System.out.println(answer);
		}
		
		
		
		
		
	}

	private static void dfs(int level, int N) {

		if (N < 0)
			return;

		if (N == 0) {
			answer++;
			return;
		}

		else {

			for (int i = 0; i < nums.length; ++i) {
				dfs(level + 1, N - nums[i]);
			}

		}

	}
}