자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(DFS,BFS 활용_조합의 경우수_DFS)

 

 

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

예시 입력 1 

5 3

예시 출력 1

10

예시 입력 2 

33 19

예시 출력 2

818809200

 

 

강의 풀이(Time: 153ms Memory: 27MB)

 

먼저 nCr에 대해 이해보자

nCr : n개 중에 r개를 뽑는다는 의미이다

종이에는 지우고 썼다가 불편해서 블랙보드로 샀더니 비치는건 양해부탁드립니다..

{1,2,3,4,5}라는 배열처럼 5명의 학생이 있는데, 5번 학생을 뽑을 경우와 안뽑을 경우로 DFS를 접근하면 된다

 

아래처럼만 해도 nCr을 구할 수 있긴하지만, 입력값이 크다면 재귀를 많이 뻗기 때문에 오래 걸릴 것이다.

그래서 메모이제이션이 필요하다

// 메모이제이션 X
import java.util.Scanner;

public class Main {

    public int DFS(int n, int r) {
        if (n==r || r == 0) return 1;
        else return 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 k = kb.nextInt();
        System.out.println(T.DFS(n,k));

    }
}

이차원 배열 dy에 값을 저장한다.

// 메모이제이션 O
import java.util.Scanner;

public class Main {
    int[][] dy = new int[35][35]; // 입력값 최대 32보다 더 널널하게 잡음
    public int DFS(int n, int r) {
        // 이미 저장된 값이 있다면 재귀 뻗지 말고 리턴
        if (dy[n][r] > 0) return dy[n][r];
        if (n==r || r == 0) return 1;
        // 2차원 배열 dy에 저장
        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 k = kb.nextInt();
        System.out.println(T.DFS(n,k));

    }
}