[Project Euler] 15. 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

15. 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

Click 알고리즘을 배울때 비슷한 문제를 본 것 같긴 하지만.... 먼저 제가 푼 방식은 도착지부터 거꾸로 탐색하며 각각의 위치에서 갈 수 있는 수를 더해가는 식입니다. 도착지를 0,0으로 놓고, 0,j 와 i,0은 모두 1로 놓고, 1,1부터는 i-1,j와 i,j-1의 값을 더해가며 결과값을 얻었습니다.

그런데 풀고들어가서 댓글을 보니 순열공식으로 풀이가 가능하다는 군요...

식이 어떻게 유도가 되는지는 모르겠지만...

순열(順列, permutation)은 서로 다른 n 개의 원소 중에서 r 개()를 뽑아서 한 줄로 세우는 경우의 수이다.



nPr, 혹은 P(n,r) 라고 쓴다. 이 기호는 순열을 나타내는 permutation의 앞글자를 딴 것이다.

P(n,r)의 수는 다음과 같이 구할 수 있다.

이를 계승을 이용하면 다음과 같은 식으로 나타낼 수 있다.

위키백과 : 순열

그리고 이를 응용하면.... 간단한 코드가 나오는 군요.

<script>
function permutation(n, m){
 var mn = m+n;
 var result = 1;
 for(var i=0;i<n; i++){
  result *= (mn-i)/(m-i);
 }
 return result;
}
</script>