문제 번호 3518 --격자길

3518: 격자길

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 52  해결 문제 수: 24
[제출][채점상황][게시판][:]

문제 설명

n×m 격자에서 왼쪽 위(0,0)에서 오른쪽 아래(n,m)까지 갈 수 있는 길의 수를 헤아리고자 한다.

길을 갈 때 몇 가지 제약사항이 있다.
(1) 격자 위의 선을 따라간다.
(2) 아래쪽 또는 오른쪽으로만 갈 수 있다.
(3) (0,0)과 (n,m)을 잇는 대각선보다 위쪽에 있는 점들은 통과할 수 없다. (대각선에 위치하는 점은 통과할 수 있다.) 아래의 그림에서 흰점은 통과할 수 없는 점이고 검은 점은 통과할 수 있는 점이다.

예를 들어, 3×4 격자에서 갈 수 있는 길은 다음과 같이 5가지가 있다.

격자의 크기가 입력되었을 때 (0,0)부터 (n,m)까지 갈 수 있는 길의 수를 출력하는 프로그램을 작성하시오.

입력

1. 두 개의 정수 n과 m이 입력된다. (1≤n,m≤15)
2. n은 격자의 세로 크기를, m은 격자의 가로 크기를 각각 나타낸다.

출력

(0,0)에서 (n,m)까지 갈 수 있는 길의 수를 출력한다.

입력예시

3 4

출력예시

5

도움말

출처

[제출][채점상황]