BOJ 백준온라인져지 6591 이항 쇼다운 풀이

1. DP 는 당연히 안됨 (2^31 2^31) 나오면 망함

2. 이전에 사용했던 bottom-up 방식을 사용

3. 시간초과가 나네?

4. 약분을 할 수 있으면 약분을 하고 하는방식을 사용

5. N-K 를 하는데 K 가 1이면 시간초과가 나네?

6. 조건문을 넣어보자!

7. BufferedWriter 를 쓰니까 틀리네?

8. 버그!

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/6591
	* BOJ 백준온라인져지 6591 이항 쇼다운 풀이
	*/
	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	while (true) {
	String str1[] = br.readLine().split(" ");
	long N = Long.parseLong(str1[0]);
	long K = Long.parseLong(str1[1]);
	if (N == 0 && K == 0) break;
	long result = 1;
	// N! / (K! * (N - K)!)
	// 5 * 4 * 3 * 2 * 1
	// 2 * 1 * 3 * 2 * 1
	if (K > N - K) K = N - K;
	for (long i = 1; i <= K; i++) {
	result *= N--;
	result /= i;
	}
	System.out.println(result);
	}
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 두 자연수 n(n ≥ 1)과 k(0 ≤ k ≤n)로 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 231보다 작은 경우만 입력으로 주어진다.