[DFS] 7. 조합의 경우수(메모이제이션)

<<풀이>>

 

우선 구현 자체는 어렵지 않게 DFS를 활용하여 구할 수 있었지만..

 

범위 초과로 인해 계속 큰 값들은 계산 오류가 났다..

 

그래서 예전에 한 번 봤던 BigInteger가 생각이나서 시도 해봤다.

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

class Main {
    private Long DFS(Long num) {
        Long answer = num;
        if (num == 1) return answer;
        else {
            answer = answer * DFS(num - 1);
        }
        return answer;
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        Long n = Long.parseLong(arr[0]);
        Long r = Long.parseLong(arr[1]);

        System.out.println(T.DFS(n) / (T.DFS(n - r) * T.DFS(r)));
    }
}

 

 

바로 이 밑의 코드가 BigInteger를 활용한 코드이다.

이 방식으로 문제를 맞출 수 있었다.

 

여기서 주의할 점은 BigInteger를 활용한다면. 일반 연산자 ==, >=, +, * 등을 활용할 수 없고

.equals, .multiply, .subtract처럼 해야 이용이 가능하다 ㅋㅋ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

class Main {
    private BigInteger DFS(BigInteger num) {
        BigInteger answer = num;
        if (num.equals(BigInteger.ONE)) return answer;
        else {
            answer = answer.multiply(DFS(num.subtract(BigInteger.ONE)));
        }
        return answer;
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        BigInteger n = new BigInteger(arr[0]);
        BigInteger r = new BigInteger(arr[1]);

        BigInteger result = T.DFS(n).divide(T.DFS(n.subtract(r)).multiply(T.DFS(r)));
        System.out.println(result);
    }
}

 

 

-강사님 풀이-

 

확실히 내가 한 방식 보다 간단하고 직관적인 코드이다. 그리고 메모제이션을 활용해서 계산 했던 값은 저장해두고 한 번 더 나오게 되면 꺼내어 사용함으로써 시간 복잡도를 줄였다. 조합의 수를 구현하는 방식은 외워두고 잘 이용해보자!!

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

class Main {
    int[][] dy = new int[35][35];
    private int DFS(int n, int r) {
        if (dy[n][r] > 0) return dy[n][r];
        if (n == r || r == 0) return 1;
        else return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r); 
    }


    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int r = Integer.parseInt(br.readLine());
        System.out.println(T.DFS(n, r));

    }
}

 

<<추가 공부>>

 

BigInteger