[모듈식 확률과 통계] 1.경우의 수 (10)최단거리 문제 (합의법칙 관점)

[확률과통계]-[1.경우의 수]-[①순열과 조합]-[(10)최단거리 문제 (합의법칙 관점)]

최단거리 문제 (합의 법칙 관점)

바둑판모양의 도로가 있습니다. 가로선과 세로선들이 도로입니다. 도로의 한쪽 끝에서 반대편 끝까지 이동할 때, 최단거리로 이동할 수 있는 경우의 수를 구하는 문제입니다. 

1) 같은 것이 있는 순열 관점

2) 합의 법칙 관점

오늘은 두번째 방법을 설명하겠습니다. 

출발지점부터 가까운 교차점들부터 경우의 수를 세봅시다. 가장 가까운 지점까지 가는 방법은 한가지입니다. 

오른쪽과 위쪽 모든 포인트들도 다 한가지씩입니다. 

이제 아래 교차점까지 가는 경우의 수를 생각해봅시다. 

두 가지 입니다. 너무 쉬워서 미쳐 생각하기 어려운데요. 사실 이 '두 가지'라는 것은 교차점 아래와 왼쪽의 경우의 수를 더한 것입니다. 이 교차점에 도착하려면 아래점이나 왼쪽점 둘 중 하나는 무조건 지나야 하기 때문입니다. 

이런 방법으로 교자점에 도착하는 경우 수를 하나하나 찾아나갈 수 있습니다. 이렇게요

문제에 따라서 이 방법이 더 유용할 때가 있습니다.