Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

17. 정수론 및 조합론

정수론과 조합론을 배워 봅시다.

Java / Python

9. 다리 놓기

1010번

다리를 놓는 경우의 수를 구하는 문제

이번 문제는 저번 이항 계수 1 문제와 유사한 문제입니다. 즉, 조합을 이용하는 문제입니다.

N ≤ M 에서 최대한 많은 다리를 놓기 위해서 M개 중 N개를 선택해서 조합하는 방식입니다.

• Java

r, n, (n-r) 의 팩토리얼 값을 각각 구하는 지 않고, 조합의 성질을 이용하여 변형한 식을 이용했습니다. 파스칼의 법칙을 이용했습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	
	static int[][] dp = new int[30][30];
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
        
		int T = Integer.parseInt(br.readLine());

		for(int i = 0; i < T; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			
			// nCr 에서 n = M, r = N
			int N = Integer.parseInt(st.nextToken());	// N = r
			int M = Integer.parseInt(st.nextToken());	// M = n
							
			System.out.println(combi(M, N));
		}
	}
	
	static int combi(int n, int r) {
		
		if(dp[n][r] > 0) {
			return dp[n][r]; 
		}
		
		if(n == r || r == 0) {
			return dp[n][r] = 1;
		}
		
		return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
	}
}

• Python

import sys

def fact(n):
	if n <= 1:
		return 1
	return n * fact(n - 1)

T = int(sys.stdin.readline())

for _ in range(T):
	N, M = map(int, sys.stdin.readline().split())
	print(fact(M) // (fact(N) * fact(M - N)))