1010 - 다리 놓기 (조합)

---

조합풀이

 

조합공식 nCr 이용

5C3 일경우 (5-0)*(5-1)*(5-2) / (1+0)*(1+1)*(1+2) = 5*4*3 / 1*2*3 = 60 / 6 = 10  이된다.

r만큼 반복된다.

 

package test;

import java.util.Scanner;

//백준
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();

		for (int t = 0; t < tc; t++) {

			long a = sc.nextLong(), b = sc.nextLong();
			long result = 1;

			for (int i = 0; i < a; i++) {
				result = result * (b - i);
				result = result / (1 + i);

			}

			System.out.println(result);
		}
	}

}

 

적용한 소스다. 

result를 바로 적용한 이유는 숫자가 너무 커지지 않게 함이다.

 

 

 

 

속도 향상을 위해 BufferedReader 로 변경했다.

package test;

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

//백준
public class Main {

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int tc = Integer.parseInt(br.readLine());

		for (int t = 0; t < tc; t++) {

			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			
			long a = Long.parseLong(st.nextToken());
			long b = Long.parseLong(st.nextToken());
			long result = 1;

			for (int i = 0; i < a; i++) {
				result = result * (b - i);
				result = result / (1 + i);

			}

			System.out.println(result);
		}
	}

}

 

확실히 빨라진것을 확인했다.