[220808][BC][인프런](8-7) 조합의 경우 수(메모이제이션)

[honeySleepr]

📌 문제

• 문제

⭐️ 아이디어

🤔 고민한 내용

• DFS 값을 어떻게 return 받아야하지?

💪 새롭게 배운 내용

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

✅ 본인 풀이

🏋️‍♀️ 시도횟수 : n회 | ⏱ 걸린시간 : 100ms | 💾 메모리 : 100MB

public class P0807 {

    private static int count;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split("\\s");
        int n = Integer.parseInt(split[0]);
        int r = Integer.parseInt(split[1]);

        /* 계산 시간 절약을 위한 연산 값 저장용 */
        arr = new int[n + 1][r + 1];

        System.out.println(DFS(n, r));
        //      System.out.println("count = " + count);
    }

    private static int DFS(int n, int r) {
        //      count++;
        if (arr[n][r] != 0) { /* 메모이제이션 안쓰면 count : 1637618399, 쓰면 533*/
            return arr[n][r];
        }
        if (n == r || r == 0) {
            return 1;
        }
        return arr[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
    }
}

참고한 자료