BOJ/1010_다리 놓기

[문제]

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

[처음 생각]

겹치지 않게 n을 기준으로 했을 때, m중에서 선택하려니 조합이나 순열로 풀리지 않았다. 

그래서 반대로 m을 기준으로 했을 때, n중에서 순서없이 선택한다고 생각하니 겹치지 않게 선택할 수 있었다. m개 중에서 n개를 순서없이 선택한다면 선택된 점들은 n개의 점과 차례대로 그냥 이어지면 되기 때문!

[풀이]

조합 알고리즘으로 mCn으로 풀었다. 

함수 재귀 호출로 점화식을 사용해서 풀었다. 

[참고]

http://bumbums.tistory.com/2

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1010/MakeBridge.java