Key Point

이전에는 n의 범위가 0<=n<=10 까지이므로 모든 경우의 수를 다 진행해보았다.
하지만, 재귀 함수를 이용해서 문제를 풀면 더욱 간단하게 풀 수 있다.

Explain

go(count, sum, goal)라는 재귀 함수를 만들어서 사용한다.

  • 불가능한 경우 : 합이 만드려는 수보다 커지는 경우 : sum > goal
  • 정답을 찾은 경우 : sum == goal
  • 다음 경우
  1. go(count+1, sum+1, goal)
  2. go(count+1, sum+2, goal)
  3. go(count+1, sum+3, goal)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Exam9095_Recursive {
	
	public static int go(int count, int sum, int goal) {
		if(count>10) {
			return 0;
		}
		if(sum == goal) {
			return 1;
		}
		
		int now = 0;
		for(int i=1;i<=3;i++) {
			now = now + go(count+1, sum+i,goal);
		}
		return now;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int test_case = Integer.parseInt(bf.readLine());
		while(test_case-- >0) {
			int number = Integer.parseInt(bf.readLine());
			System.out.println(go(0,0,number));
		}
	}

}