9095번 - 1, 2, 3 더하기

1️⃣ DFS

 

✏️ 풀이 과정

DP문제라고 되어있으나 n이 최대 11로 작기 때문에 DFS로도 빠르게 해결할 수 있습니다.

 

0부터 시작해서 입력+1, 입력+2, 입력+3으로 재귀적으로 DFS를 실행하면서 숫자가 n보다 같거나 클 때 리턴하고 같은 경우를 카운팅해주면 됩니다.

 

💻 코드

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

public class Main {
	
	static int n;
	static int cnt;
	
	static void dfs(int N) {
		if(N >= n) {
			if(N == n) {
				cnt++;
			}
			return;
		}
		dfs(N+1);
		dfs(N+2);
		dfs(N+3);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t=0;t<T;t++) {
			n = Integer.parseInt(br.readLine());
			cnt = 0;
			dfs(0);
			sb.append(cnt+"\n");
		}
		System.out.print(sb);
		br.close();
	}
}