백준 1010 자바 - 다리 놓기 (BOJ 1010 JAVA)

문제 : https://www.acmicpc.net/problem/1010

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1010.java

 

  N=2, M=3인 경우를 보자.

1

 

2

3

 

이런식으로 가능하다. 그럼 좌측은 생각하지 말고, 우측 중 선택된 녀석들만 확인해보자.

 

위와 같다. 즉 선은 생각하지 말고, 어차피 M개 중 N개만 선택하면 되는 문제이다. 이 때 다리가 서로 겹칠 수 있다고 한다면 nPm 이겠지만, 서로 겹칠 수 없다고 했으므로 nCm이 된다. 왜냐하면 겹칠 수 있다면 다음과 같이도 놓을 수 있기 때문이다.

 

nCm = nPm / n! 을 구하면 된다.

예를들어 N = 3, M = 5 라면

nCm = 5*4*3 / 3*2*1 = 10 이다.

 

코드의 경우 2년전에 풀었던건데 특이하게 double로 해놨다 ㅋㅋ 어차피 풀이만으로 푸는덴 문제없으므로 신박해서 다시 코드를 작성하지 않고 그대로 올려봤다. Math.pow(10, -9) 를 통해 오차를 어느정도 조정하고 정수형으로 바꿔서 출력했다. 2년전에 난 많이 창의적이었던 것 같다.