이동 경로의 가지수를 구하라.

문제

본인이 프로그래밍을 한 이후에 올바르게 값이 출력이 되는지 궁금할 것이다.

이 문제에서 구하는 경로의 개수는 아래와 같이 표현된다.

 

위와 같이 식이 세워지는 이유를 찾아보자.

X번 오른쪽으로, 그리고 Y번 아래쪽으로 진행하여 만들 수 있는 모든 경로의 수를 세야 한다.

이 경로는 ( X + Y ) 개의 이동 단계로 구성된다.

경로 하나를 만들려면, X + Y 번 이동하는 가운데 X번은 오른쪽으로 움직이도록 해야 한다.

그러므로, 전체 경로의 수는 ( X + Y ) 가운데 X의 항목을 뽑는 경우의 수와 같다.

그래서, 위와 같은 이항식이 나온다.

 

문제 분석

위의 문제의 초점은 로봇이 움직이는 방향이다.

로봇은 두 방향으로만 움직이는 것이 가능하다.

그리고, 시작위치와 끝 위치가 주어져 있다.

여기서 역으로 시작위치에서 끝 위치로 이동해가면서 경로를 파악하는 것이 아니라,

그 반대로 끝 위치에서 시작위치로 되돌아가면서 경로를 파악하자.

그러면, 여기서 가장 중요한 것이 끝 위치의 바로 앞에 오는 경우를 구하는 것이 핵심이다.

( 여기서 방향이 중요하다. )

이 것을 점화식으로 써보도록 하자.

 

 

구현

프로그램 실행결과

 

소스 파일

main.c

0.00MB