순열을 이용한 최단 경로의 경우의 수

순열을 이용한 최단 경로의 경우의 수 [예제] 이 문제를 어떻게 풀까? 순열을 이용하면 된다.

우선 한번 고민해 보자. 문제를 아래와 같이 간단히 해 보자.

아래의 가운데 점까지 가는 방법이 왼쪽에서 오는 방법이 a개이고, 아래서 오는 방법이 b개 라면, 가운데 점까지 오는 방법의 수는 a+b개이다. 이런식으로 생각하면, 아래와 같다.

A점에서 한칸 위, 한칸 오른쪽으로 가는 방법은 1+1 해서 2가지가 된다. 이런 식으로 더해 나가면, 아래와 같이 된다.

A에서 B로 가는 방법의 수는 35가지라는 것을 무식하게 알아 냈다. 이번에는 순열을 이용하여 풀어보자.

왼쪽에서 오른쪽으로 한칸 이동하는 것을 a 라고 하고 위로 한칸 이동하는 것을 b라고 하면 aaaabbb bbbaaaa abababa ... 와 같이 여러가지 방법이 있다.

이런식으로 a를 4번 b를 3번 써서 나열하는 방법은 번이다. 이를 계산하면 35이다.

[모든 최단 방법] 그렇다면 위의 예제에서 P 점은 통과하는 것과 ...