[백준] 합분해 - 실패

참고 : www.acmicpc.net/problem/2225

2225번: 합분해

- dp 문제

- dp[i][j] : i를 구하기 위해 필요한 j 횟수 (0~i 까지 숫자를 이용)

 

- dp 로 해야했으나 recursive하게 backtracking 으로 접근 : 실패

 

import java.io.*;
import java.util.*;

public class Solution {

    private static int n, m;
    private static int[] arr;
    private static boolean[] isUsed;
    private static int count = 0;
    private static int MOD = 1_000_000_000;

    private static void bt(int k) {
        if(k == m) {
            int sum = 0;
            for (int i = 0; i < m; i++) {
//                System.out.print(arr[i] + " ");
                sum += arr[i];
            }
//            System.out.println();
            if(sum == n) {
//                System.out.println(sum);
                count++;
            }
            return;
        }
        for (int i = 0; i <= n; i++) {
//            if(!isUsed[i]) {
                arr[k] = i;
//                isUsed[i] = true;
                bt(k+1); // 뎁스 1 증가
//                isUsed[i] = false;
//            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[202];
        isUsed = new boolean[202];
        bt(0);
        System.out.println(count%MOD);
    }
}