최단 경로 계산하기 - 2015 정보올림피아드 문제풀이

올해 올림피아드 예선에 아들을 데려다 주고 집에 오면서 들은 질문입니다. 내 아들이지만 머리속에 들어있는 생각은 도통 알수 없군요. 아무튼 질문을 받았으니 답을 주어야 겠지요. 이 문제는 최단 경로 계산하기라는 전형적인 문제입니다. 계산 공식에는 팩토리얼(factorial, 계승)이 쓰이므로 팩토리얼은 알아야겠지요. n 팩토리얼이라 함은 0부터 n까지의 자연수를 곱한값을 의미하고 n!로 표시합니다. 3팩토리얼은 3!로 표시하고 1X2X3의 값인 것입니다. 0부터 8까지의 팩토리얼 값은 0, 1, 2, 6, 24, 120, 720, 5040, 30320 입니다.

문제는 다음과 같았습니다.

C를 들러서 A에서 B까지 가는 최단 경로는 A에서 C까지 갈수 있는 최단 경로의 수에 C에서 B까지 갈수 있는 최단 경로의 수를 곱한 것으로 구할 수 있습니다.

정사각형으로 표시된 경로를 아래의 그림과 같이 가로 경로를 a, 세로 경로를 b라고 할때 최단 경로의 개수는 가로경로의 문자열 aaaaa와 세로 경로의 문자열 bb로 배열할 수 있는 문자열의 개수로 구할 수 있습니다.

그 공식은 다음과 같습니다.

위의 문제의 경우에는 다음과 같은 식으로 값을 구할 수 있습니다.