[Python][Java] 백준 2407번 - 조합

https://www.acmicpc.net/problem/2407

2407번: 조합

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 수학
 - 조합론
 - 임의 정밀도 / 큰 수 연산

 

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

 

---

우선 nCm이 뭔지 까먹어서 검색한 사람도 많을 테니 간단하게 보고 가자.

 

로또복권은 1 부터 45라는 숫자 중에 6개를 선택해서 당첨을 하는 복권이다.
1등에 당첨 될 확률(경우의 수)은 얼마?



:: 설명 ::

45개의 숫자를 6가지로 조합할 수 있는 경우 수 = 45C6


1) 계승(팩토리얼, factorial)
    해설:           1부터 어떤 양의 정수 n까지를 곱한 것.
    표기법:         n!
     예 :             6! = 1 x 2 x 3 x 4 x 5 x 6
                       1 부터 6까지 모두 곱함.
    발음:           육팩토리얼 이라고 읽음.

2) 수열(퍼뮤테이션, permutation)
    해설:           n 의 수를 m 까지 n-1 씩하여 곱한 것.
    표기법:         nPm
     예 :            45P6  = 45 x 44 x 43 x 42 x 41 x 40
                      m이 6 이기 때문에 (n - i) 한걸 모두 곱합 (i 는 0 부터 해서 6번)
    발음:           사십오 퍼뮤테이션 육 이라고 읽음.


3) 조합(콤비네이션, combination)
    해설:           순서를 따지지 않은 숫자의 집합 
    표기법:         nCm
     예 :             nCm=  nPm  ÷  m!
                       45C6 =  45P6  ÷  6!
    발음:           사십오 콤비네이션 육 이라고 읽음.

 

출처: http://egloos.zum.com/js7309/v/11112494

[ICPC]조합 nCm

 

즉, 우리가 구해야할 nCm은

 

n * (n-1) * (n-2) * .... * (n-m+1) / ( m * (m-1) * (m-2) * ... * 1)

위와 같이 나타낼 수 있다.

 

Python Code

import sys
import math
input = sys.stdin.readline
n, m = map(int, input().split())
ans = math.factorial(n) // math.factorial(n-m)//math.factorial(m)
print(ans)

math 라이브러리의 factorial 함수를 사용했다.

 

나누기를 3번 사용한 이유는

 

n * (n-1) * (n-2) * .... * (n-m+1) 이 구간이

n! / (n-m)! 과 동일하기 때문이다.

 

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		BigInteger ans = new BigInteger("1");

		for( int i=n; i>m; i--) {
			ans = ans.multiply(BigInteger.valueOf(i));
		}
		for(int i=n-m; i>1; i--) {
			ans = ans.divide(BigInteger.valueOf(i));
		}
		System.out.println(ans);
	}

}

아마 많은사람들이 위와 같이 해결했을 것이다.

 

반복문을 통해서