백준/11050 이항 계수 1 // 조합 -> (dfs + 백트래킹) or 재귀

이항 계수 1 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

42298

27353

23597

64.534%

문제

자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 10, 0 ≤ K\(K\) ≤ N\(N\))

출력

 (NK)\(\binom{N}{K}\)를 출력한다.

예제 입력 1 복사

5 2

예제 출력 1 복사

10

---

풀이

조합을 이용해 풀이

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


   static int n;
   static int k;
   static int result;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        visited = new boolean[n];

        combination(0, 0);
        bw.write(result+"");

        bw.flush();
        bw.close();

    }

    public static void combination(int start, int count) {
        if (count == k) {
            result++;
            return;
        }
        for (int i = start; i < n; i++) {
            if(!visited[i]){
                visited[i] = true; //해당 값 선택
                combination(i + 1, count + 1);
                visited[i] = false;
            }


        }

    }



}

 

1. 조합 구현 : dfs (+백트래킹)

 

 

2. 조합구현 : 재귀 

public static void combination( int count,int depth) {
    if (count == k) { //다 선택한경우
        result++;
        return;
    }
    if (depth == n) {
        return;
    }
    visited[depth] = true;
    combination(count + 1, depth + 1);
    visited[depth] = false;
    combination(count, depth + 1);

}