[수학] 백준 - 이항 계수 1

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

11050번: 이항 계수 1

-문제해설

그냥 조합을 구하면 되는 문제이다. n개 중에서 순서에 상관없이 k개를 뽑을 경우의 수.

수학적으로 조합 식에 해당되는 분자를 구하고

조합 식에 해당되는 분모를 구한 뒤 두 개를 나눠도 되지만

 

예전에 조합을 다이나믹프로그래밍을 이용해서 구한 적이 있어서 dp로 풀었다.

1C0 =1  1C1 =1

2C0 =1  2C1 =2  2C2 =1

3C0 =1  3C1 =3  3C2 =3   3C3 =1

4C0 =1  4C1 =4  4C2 =6   4C3 =4  4C4 =1

5C0 =1  5C1 =5  5C2 =10  5C3=10 5C4 =5  5C5 =1

 

(i)C(j) 라고 할 경우 규칙을 확인해보면 j가 0이거나 i이면 1이고

그 외에 (i)C(j) = (i-1)C(j-1) + (i-1)C(j) 인 것을 알 수 있다.

 

이를 코드로 구현하면 아래와 같다.

 

 

-자바

package math;

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

public class BJ11050 {
	private static int n, k;
	private static int[][] d;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		k = Integer.parseInt( st.nextToken() );
		
		d = new int[n+1][];
		d[1] = new int[2];
		d[1][0] = d[1][1] = 1;
		for( int i=2; i<=n; i++ ) {
			d[i] = new int[i+1];
			for( int j=0; j<=i; j++ ) {
				if( j==0 || j==i ) d[i][j] = 1;
				else d[i][j] = d[i-1][j-1] + d[i-1][j];
			}
		}
		System.out.println( d[n][k] );
	}
}

 

-파이썬

n, k = map(int, input().split())
d = list( [0] * (n+1) )
d[1] = [1, 1]
for i in range( 2, n+1 ):
    d[i] = list( [0] * (i+1) )
    for j in range( 0, i+1 ):
        if j==0 or j==i: d[i][j] = 1 
        else: d[i][j] = d[i-1][j-1] + d[i-1][j] 
print( d[n][k] )