2002년 가을학기 문제해결기법  기말고사

최단 경로의 수

행의 수가 이고 열의 수가 인 격자판이 있다. 이 격자판의 행 번호는 1부터 까지 열 번호는 1부터 까지 번호가 붙어 있다. 격자점의 좌표는 열 번호와 행 번호의 순서쌍으로 표현하기로 한다.

아래 그림은 행의 수가 4이고 열의 수가 5인 격자판이다. 이 격자판의 맨 오른쪽 위 격자점의 좌표는 (5,4)이다.

행의 수가 이고 열의 수가 인 격자판에서 왼쪽 아래 격자점 (1,1)에서 오른쪽 위 격자점 (,)까지 서로 다른 최단 경로의 개수를 구하고자 한다. 인접한 격자점 사이의 거리는 1이고, 격자판의 가로선과 세로선 위로만 경로가 지나갈 수 있다고 가정한다. 위 그림에 격자점 (1,1)에서 (5,4)까지의 경로 하나가 굵은 실선으로 표시되어 있다.

구하고자 하는 최단 경로의 개수는 , 이 그리 크지 않은 정수일 때도 상당히 클 수 있다. 격자점 (1,1)에서 (,)까지 서로 다른 최단 경로의 개수를 10,000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

프로그램 이름은 path.xxx, 실행 파일 이름은 path.exe로 한다. 프로그램의 실행 시간은 1초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 행의 수 과 열의 수 이 주어진다. 과 은 모두 1 이상 100 이하인 양의 정수이다. 입력되는 두 정수 사이에 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째줄에 최단 경로의 개수를 10,000으로 나눈 나머지를 출력한다.

입력과 출력의 예 (1)

INPUT.TXT

2 3

OUTPUT.TXT

3

입력과 출력의 예 (2)

INPUT.TXT

10 10

OUTPUT.TXT

8620

채점 기준

테스트 데이터 10개에 대하여, 올바른 답을 출력하는 테스트 데이터의 수에 따라 아래와 같이 점수를 배정한다.

10	9	8	7	6	5	4	3	2	1	0
100	67	44	30	20	13	9	6	4	2	0