[백준 | Java] 9095 1, 2, 3 더하기

내 풀이

이 문제는 푸는 방법이 다음 두 가지가 있다.

• 브루트포스 백트래킹(재귀) 탐색
• DP

그 중 나는 브루트포스 백트래킹(재귀) 탐색 방법으로 풀었고, 풀이과정은 다음과 같다.

1. i가 1부터 4까지 n-i를 하며 0이 될 때 까지 재귀 탐색 진행
2. n이 0이 되면 정답 개수 1 추가

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

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

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            cnt = 0;
            int n = Integer.parseInt(br.readLine());
            backTracking(n);
            System.out.println(cnt);
        }
    }

    static void backTracking(int n) {
        if (n == 0)
            cnt++;

        for (int i = 1; i < 4; i++) {
            int check = n-i;
            if (check >= 0)
                backTracking(check);
        }
    }
}