[백준 알고리즘] 백준 2407번 조합 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 2407번 조합 자바(Java)

1) 문제번호 : 2407번

 

2) 문제 출처

www.acmicpc.net/problem/2407

2407번: 조합

 

2. 문제

nCm을 출력한다.

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

nCm을 출력한다.

 

6. 풀이

- 재귀로 풀으니 시간초과가 난다.

- 그래서, BigInteger 이용하고, 결국엔 n1은 nCr 구하는 공식의 분자가 되고, n2는 분모가 된다.

- nCr = n-1Cr-1 + n-1Cr

 

7. 소스 코드

import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		BigInteger n1 = BigInteger.ONE;
		BigInteger n2 = BigInteger.ONE;
		
		for(int i=0;i<m;i++) {
			n1 = n1.multiply(new BigInteger(String.valueOf(n-i)));
			n2 = n2.multiply(new BigInteger(String.valueOf(i+1)));
		}
		
		System.out.println(n1.divide(n2));
	}
	
	
}

- 재귀로 풀었지만, 시간 초과

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		System.out.println(combination(n,m));
	}
	
	public static int combination(int n, int m) {
		if(n==m || m ==0) return 1;
		
		return combination(n-1, m-1) + combination(n-1, m);
	}
}

---