[백준] | JAVA, 자바 | 9095번 - 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

---

문제 요약 :

1. 테스트 케이스의 개수 T 입력받기

2. T 만큼 정수 N 입력받기

3. 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성

---

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

public class Main {
    private static int num;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 1. 테스트 케이스의 개수 T 입력받기
        int t = Integer.parseInt(br.readLine());

        // 2. T 만큼 정수 N 입력받기
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            num = 0;
            dfs(0, n, 0);
            sb.append(num).append("\n");
        }
        // 3. 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성
        System.out.println(sb);
    }

    // dfs를 통해 1, 2, 3 을 더 했을 때, idx값이 된다면 num_++
    private static void dfs(int total, int idx, int cnt) {
        if (total == idx) {
            num++;
            return;
        }

        if (total > idx) return;

        dfs(total + 1, idx, cnt + 1);
        dfs(total + 2, idx, cnt + 1);
        dfs(total + 3, idx, cnt + 1);
    }
}