문제
문제이해
강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 하고 서쪽에는 N개 동쪽에는 M개의 사이트가 있다(n <= m)
다리는 한사이트에 최대 한개만 연결될 수있고 서로 겹칠 수 없을 때 다리를 지을 수 있는 경우의 수를 모두 구하는 문제이다
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
- T
- N M (N 과 M는 공백으로 구분되어 입력)
출력
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다
풀이
한 사이트는 최대 한 개의 다리만 연결되는 것과 다리가 서로 겹칠 수 없는 단서를 확인한다면 조합 문제라는 것을 알 수 있습니다. 그렇다면 문제는 mCn을 구하는 문제가 되며 이는 m! 을(m-n)!n!으로 나눈 값이 된다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int test_case = sc.nextInt();
for(int i = 0; i < test_case; i++){
int n = sc.nextInt();
int m = sc.nextInt();
int answer = 1;
// n == m 이면 경우의 수가 1개
if(n == m)answer = 1;
else{
// nCr 계산
for(int j = 0; j < n; j++){
answer *= m-j;
answer /= 1+j;
}
}
System.out.println(answer);
}
}
}
'Algorithm > 문제' 카테고리의 다른 글
[알고리즘] 백준 5585 : 거스름돈 - JAVA (0) | 2023.04.06 |
---|---|
[알고리즘] 백준 1931 : 회의실 배정 - JAVA (0) | 2023.04.06 |
[알고리즘] 백준 1009 : 분산처리 - JAVA (0) | 2023.04.04 |
[알고리즘] 백준 13458 : 시험 감독 - JAVA (0) | 2023.04.03 |
[알고리즘] 백준 14501 : 퇴사 - JAVA (0) | 2023.04.03 |