[문제풀이] 08-07. 조합 수

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0807. 조합수(메모이제이션)

🗒️ 문제

🎈 나의 풀이

	private static int C[][];

    private static int DFS(int n, int r) {
        if(n == r) return 1;
        if(r == 1) return n;
        if(C[n][r] == 0) C[n][r] = DFS(n-1, r-1) + DFS(n-1 , r);
        return C[n][r];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        C = new int[n+1][r+1];

        System.out.println(DFS(n , r));

    }

🖍️ 강의 풀이

  	int[][] dy=new int[35][35];
	public 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){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int r=kb.nextInt();
		System.out.println(T.DFS(n, r));
	}

💬 짚어가기

해당 문제는 순열 공식 $_{n}C_{r}$ $=$ $_{n-1}C_{r-1}$ $+$ $_{n-1}C_{r}$에 맞추어 DFS를 이용하여 풀 수 있다.
n과 r을 파라미터로 전달 받고, 재귀호출하여 n-1, r-1과 n-1, r을 넘긴다.
조건을 두어 n==r인 경우 1을 반환하고, r==1인 경우 n을 반환한다.

이 때, 이미 구한 조합에 대해 재귀 호출을 수행하게 되면 중복적으로 연산을 하게된다.

메모이제이션
해당 조합을 이미 구한 경우 배열에 저장된 값을 사용하도록한다.